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


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.

  • 2
    $\begingroup$ 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). $\endgroup$ Commented Oct 14, 2010 at 18:31
  • $\begingroup$ @Tsuyoshi: You're right! Fixed. $\endgroup$ Commented Oct 14, 2010 at 18:48

1 Answer 1


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.


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.