patternMinor
Results on the difficulty of specific random 3-SAT problems?
Viewed 0 times
randomsatthedifficultyspecificresultsproblems
Problem
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:
As illustrated above, both the number of solutions and the time to run can fluctuate significantly; is there any relationship between the two?
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?
Solution
Research has concentrated not on the number of satisfying assignments, but on the clause density $\alpha$. It is (more or less) known that:
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$.
- 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.
- After a certain threshold, there are no satisfying assignments (with high probability).
- 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$.
Context
StackExchange Computer Science Q#53788, answer score: 8
Revisions (0)
No revisions yet.