3
$\begingroup$

Is there any parallel algorithms or approximation algorithms for 3SAT?

$\endgroup$
  • 3
    $\begingroup$ 3-SAT is a decision problem. There are no approximation algorithms for decision problems, as the answer is always either “yes” or “no.” Perhaps you are looking for its optimization variant, MAX-3-SAT? $\endgroup$ – Sacha Dec 30 '10 at 12:55
  • 1
    $\begingroup$ Parallel and approximation algorithms are quite different. It would be nice if you provide some motivation and explain why you are interested in this question since this does not seem to be a research-level question. Please read the site's FAQ and How to ask a good question?. $\endgroup$ – Kaveh Jan 2 '11 at 6:00
6
$\begingroup$

Take a look at this question for some pointers to SAT solvers. Specially, there's a link to SAT Competition, in which you can find parallel SAT solvers (like ManySAT or gNovelty2+).

$\endgroup$
  • $\begingroup$ ManySAT isn't truly parallel in this sense it employs sequential solvers on different cores with different heuristics. It doesn't make the problem smaller and also can't be readily scaled since new workers (threads or processes) need carefully designed different heuristics. $\endgroup$ – user Nov 1 '14 at 23:50
4
$\begingroup$

There are some approaches to distributed constraint satisfaction problems. Check out this paper.

http://portal.acm.org/citation.cfm?id=627939

Majority of them are embarrassingly parallel, where each node chooses a starting point, implements a serial solver etc. The smart bit comes in, in communicating dead end paths to other nodes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.