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

  • 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
    Commented Dec 30, 2010 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
    Commented Jan 2, 2011 at 6:00

2 Answers 2


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+).

  • $\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
    Commented Nov 1, 2014 at 23:50

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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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