Results on the difficulty of specific random 3-SAT problems?

Question

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?

Answer 1

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$.