<p>The answer is no.  If you consider a graph with satisfying assignments as vertices where two assignments are joined by an edge if the Hamming distance is 1, the graph is always connected because every satisfying assignment can be eventually transformed to the all-1 assignment by changing the value of one variable from 0 to 1.</p>

CC BY-SA 2.5
2010-10-14T18:55:32.873Z
2010-10-14T18:55:32.873Z
Tsuyoshi Ito
<p>It is known that generic k-SAT formulas may exhibit the presence of exponentially many solution clusters.</p>
<blockquote>
<p><strong>Question:</strong></p>
<p>Is it true also for Monotone-2SAT formulas?</p>
</blockquote>
<p>For the definition of cluster, see Kaveh's answer to the question <a href="https://cstheory.stackexchange.com/questions/1115/sat-solution-space-definition-of-cluster-of-solutions">SAT Solution Space - Definition of Cluster of Solutions</a>.</p>

CC BY-SA 2.5
2010-10-14T18:31:30.037Z
If you remember your older question asking the definition of “cluster,” please do not let people go through the same trouble as the one you experienced.  That is, define “cluster” in your question (or give a link to the definition you intend if the definition is too long to include in the question).
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-14T18:48:57.527Z
@Tsuyoshi: You're right! Fixed.
Giorgio Camerani
<cc.complexity-theory><ds.algorithms><sat><counting-complexity>
Solution Clusters and Monotone-2SAT
Giorgio Camerani
# Solution Clusters and Monotone-2SAT

(Asked by: username_0 on 2010-10-14)

It is known that generic k-SAT formulas may exhibit the presence of exponentially many solution clusters.

> **Question:**
>
> Is it true also for Monotone-2SAT formulas?

For the definition of cluster, see Kaveh's answer to the question [SAT Solution Space - Definition of Cluster of Solutions](https://cstheory.stackexchange.com/questions/1115/sat-solution-space-definition-of-cluster-of-solutions).

**Tags:** cc.complexity-theory, ds.algorithms, sat, counting-complexity
> **Comments:**
> **username_1**: If you remember your older question asking the definition of “cluster,” please do not let people go through the same trouble as the one you experienced.  That is, define “cluster” in your question (or give a link to the definition you intend if the definition is too long to include in the question).  
> **username_0**: @Tsuyoshi: You're right! Fixed.  

---

## 1 answers

### Answer by username_1 on 2010-10-14. Score: 8 | Accepted answer

The answer is no. If you consider a graph with satisfying assignments as vertices where two assignments are joined by an edge if the Hamming distance is 1, the graph is always connected because every satisfying assignment can be eventually transformed to the all-1 assignment by changing the value of one variable from 0 to 1.


---

