<p>There are some approaches to distributed constraint satisfaction problems.  Check out this paper.</p>

<p><a href="http://portal.acm.org/citation.cfm?id=627939" rel="nofollow">http://portal.acm.org/citation.cfm?id=627939</a></p>

<p>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. </p>

CC BY-SA 2.5
2010-12-30T14:28:16.210Z
2010-12-30T14:28:16.210Z
Alex Gonopolskiy
<p>Take a look at <a href="https://cstheory.stackexchange.com/q/1060/873">this question</a> for some pointers to SAT solvers. Specially, there's a link to <a href="http://www.satcompetition.org/" rel="nofollow noreferrer">SAT Competition</a>, in which you can find parallel SAT solvers (like <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.159.6667&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">ManySAT</a> or gNovelty2+).</p>

CC BY-SA 3.0
2014-11-01T23:50:49.740Z
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.
user
CC BY-SA 2.5
2010-12-30T13:06:26.363Z
2010-12-30T13:06:26.363Z
2017-04-13T12:32:28.167Z
Sadeq Dousti
<p>Is there any parallel algorithms or approximation algorithms for 3SAT?</p>

CC BY-SA 2.5
2010-12-30T12:55:05.517Z
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?
Sacha
CC BY-SA 2.5
2011-01-02T06:00:00.050Z
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](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science) and [How to ask a good question?](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question).
Kaveh
<cc.complexity-theory><sat><approximation-algorithms><dc.parallel-comp>
Is there parallel algorithm for 3SAT
misagh
# Is there parallel algorithm for 3SAT

(Asked by: username_0 on 2010-12-30)

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

**Tags:** cc.complexity-theory, sat, approximation-algorithms, dc.parallel-comp

> **Comments:**
> **username_1**: 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?  
> **username_2**: 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](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science) and [How to ask a good question?](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question).  

---

## 2 answers

### Answer by username_4 on 2010-12-30. Score: 6 | Accepted answer

Take a look at [this question](https://cstheory.stackexchange.com/q/1060/873) for some pointers to SAT solvers. Specially, there's a link to [SAT Competition](http://www.satcompetition.org/), in which you can find parallel SAT solvers (like [ManySAT](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.159.6667&rep=rep1&type=pdf) or gNovelty2+).

> **Comments:**
> **username_5**: 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.  

---

### Answer by username_3 on 2010-12-30. Score: 4

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.


---

