Computing in the fractal cloud: modular generic solvers for SAT and Q-SAT variants

Abstract geometrical computation can solve hard combinatorial problems efficiently: we showed previously how Q-SAT can be solved in bounded space and time using instance-specific signal machines and fractal parallelization. In this article, we propose an approach for constructing a particular generi...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2011-05
Main Authors: Duchier, Denys, Durand-Lose, Jérôme, Senot, Maxime
Format: Article
Language:English
Subjects:
Combinatorial analysis
Fractals
Modular construction
Modular structures
Parallel processing
Solvers
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Abstract geometrical computation can solve hard combinatorial problems efficiently: we showed previously how Q-SAT can be solved in bounded space and time using instance-specific signal machines and fractal parallelization. In this article, we propose an approach for constructing a particular generic machine for the same task. This machine deploies the Map/Reduce paradigm over a fractal structure. Moreover our approach is modular: the machine is constructed by combining modules. In this manner, we can easily create generic machines for solving satifiability variants, such as SAT, #SAT, MAX-SAT.
ISSN:2331-8422