3
$\begingroup$

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.

Improve this question
$\endgroup$
  • 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$ – Tsuyoshi Ito Oct 14 '10 at 18:31
  • $\begingroup$ @Tsuyoshi: You're right! Fixed. $\endgroup$ – Giorgio Camerani Oct 14 '10 at 18:48
8
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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