3
$\begingroup$

What is the relationship between the number of clauses and the difficulty of a 3-SAT problem?

$\endgroup$
3
  • $\begingroup$ What do you mean by the "difficulty" of a 3-SAT problem? Problems, for example, may belong to $P$ and $NP$ classes. $NP$-complete problems are considered hard. 3SAT (with arbitrary number of clauses) problem is NP-complete. But if you consider a class of 3SAT problems with fixed number of clauses then it is clearly in $P$ since it is decidable in $O(1)$ time. $\endgroup$
    – fade2black
    Nov 7 '17 at 21:59
  • 1
    $\begingroup$ Difficulty is affected both by number of unique clauses and variables. Too many unique clauses [compared to variables] may make the problem too easy. $\endgroup$
    – rus9384
    Nov 7 '17 at 22:46
  • 1
    $\begingroup$ Related: arxiv.org/abs/1411.0650 and also demonstrations.wolfram.com/TheSatisfiabilityThreshold $\endgroup$
    – ryan
    Nov 8 '17 at 3:01
4
$\begingroup$

In general, there is no connection. An instance with a "small" number (say a few thousands) of clauses can be very difficult to solve in practice, while an instance with a "large" number (say several millions) of clauses is easy. It's the structure that matters, not the number of clauses.

For random 3-SAT, you can have a look at the satisfiability threshold.

$\endgroup$
1
$\begingroup$

So, this all depends on what you mean by relationship.

In terms of traditional time complexity, all known algorithms solving 3SAT are, at best, exponential. To be precise, this means that if $f(n)$ is the function mapping an input size $n$ to the maximum time the algorithm takes on any input of size $n$, then $f$ is in $\Theta(b^n)$ for some $b \geq 1$.

However, in practice, adding clauses can speed things up, particularly if they are the right clauses. This is how, for example, Conflict Driven Clause Learning works. When backtracking search fails, CDCL "learns" a new clause which must be true (or else the search wouldn't have failed). It can then restart its search. The additional clauses add constraints that, when unit propagation is performed (i.e. when $p$ holds, we remove all $\lnot p$ occurrences from clauses), can prune out large portions of the search space.

$\endgroup$
0
$\begingroup$

3-SAT is a decision problem, like all NP-complete problems (because that's the way NP is defined). So you look at an instance of the problem, and have to decide whether the answer is YES or NO.

For most NP-complete problems, you can find sequences of instances that start with an instance where it is very easy to prove that the answer is YES, and as you look at other instances this becomes harder and harder to proof, then the correct answer changes to a very hard to prove NO, and further instances make it easier and easier to prove that the answer is NO.

That's what happens if you add more and more clauses to a 3-SAT instance. As you add clauses, it gets harder and harder to satisfy them all. And then you add one more clause that makes it impossible to satisfy all the clauses, which will be very hard to prove. As you add more and more clauses, that proof gets easier.

$\endgroup$

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