Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a companion question to Results on number of solutions to random 3-SAT?

Let $A$ and $B$ be two problems drawn from random 3-SAT, both with the same number of variables and clauses. If $A$ has fewer satisfying assignments than $B$, do SAT solvers perform worse when trying to solve $A$ vs. $B$? Are there any results on this? (I'm a physicist by training, so a follow-up would be: is this even an interesting CS problem?)

EDIT: I wrote a quick little DPLL-based program to calculate the number of satisfying assignments for $\alpha = 4$ and $N = 80$. Here are the # of solutions and time to complete for a few random runs to illustrate the phenomenon that I'm looking for insight into:

  • 368 solutions, 2.2 s
  • 192 solutions, 8.4 s
  • UNSAT, 3.2 s
  • 50492 solutions, 2.6 s
  • 1212 solutions, 13.9 s

As illustrated above, both the number of solutions and the time to run can fluctuate significantly; is there any relationship between the two?

share|cite|improve this question

Research has concentrated not on the number of satisfying assignments, but on the clause density $\alpha$. It is (more or less) known that:

  1. Below a certain threshold, the problem is easy. Moreover, the solution set is "continuous" (with high probability), in that all solutions are (more or less) connected.
  2. After a certain threshold, there are no satisfying assignments (with high probability).
  3. Between the two thresholds, the instance is satisfiable (with high probability), but a satisfying assignment is conjectured to be hard to find. Moreover, the solutions belong to exponentially many small clusters that are "far away" from each other: any path connecting them goes through an assignment that satisfies a relatively small fraction of clauses.

These thresholds have been calculated by physicists, but their work is not mathematically rigorous. Rigorously much is known, especially for random $k$-SAT and similar problems for large $k$, but the actual behavior for 3SAT hasn't been rigorously proven.

The literature on the area is enormous, but unfortunately I can't find a recent survey, though these probably do exist. You can start by reading a very short, relatively recent survey by Coja-Oghlan. A recent important rigorous result is Ding, Sly and Sun, who prove rigorously that the unsatisfiability threshold for $k$-SAT exists for large enough $k$.

share|cite|improve this answer
    
Thanks for those links, it'll give me something to read on the flight back. This isn't quite what I'm looking for, though, so I've edited my question to provide some examples. – Andrew Mar 1 at 15:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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