Is there any parallel algorithms or approximation algorithms for 3SAT?
$\begingroup$
$\endgroup$
2
-
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$– SachaCommented 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$– KavehCommented Jan 2, 2011 at 6:00
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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+).
answered Dec 30, 2010 at 13:06
-
$\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$– userCommented Nov 1, 2014 at 23:50
$\begingroup$
$\endgroup$
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.
