5
$\begingroup$

I've been trying to investigate 3-SAT for variables appearing 3 times and so far I'm getting some mixed answers as to its complexity.

For example, https://people.maths.ox.ac.uk/scott/Papers/restricted3sat.pdf says

instances of 3-SAT in which every variable occurs three times are always satisfiable (this is an immediate corollary of Hall’s Theorem), while it is NP-hard to decide the satisfiability of 3-SAT instances in which every variable occurs four times

so apparently when variables appear 3 times it's an easy problem (?).

But the following two references seem to say something else:

From here, http://www.csie.ntu.edu.tw/~lyuu/complexity/2008a/20080403.pdf,

3sat is NP-complete for expressions in which each variable is restricted to appear at most three times, and each literal at most twice.

and http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.319.8796&rep=rep1&type=pdf Lemma 5:

The SAT-3 problem is NP-complete even when each variable appears 3 times.

So is this problem NP-complete for when variables appear 3 times or 4 times? I'm pretty confused.

$\endgroup$
  • $\begingroup$ Just be careful what 3-SAT means: clauses of length at most 3, or exactly 3. If there are exactly 3 literals in every clause, the instance is always satisfiable (IIRC from Tovey's paper). Otherwise, the problem is NP-complete (you also allow for smaller clauses). $\endgroup$ – Juho Oct 19 '15 at 14:40
7
$\begingroup$

There is no conflict between your references. The problem is that they have slightly different definitions of what 3-SAT is. You need to read the (original) theorems by Tovey very carefully.

Let r,s-SAT denote the class of instances with exactly r variables per clause and at most s occurrences per variable.

[...]

Theorem 2.1. Boolean satisfiability is NP-complete when restricted to instances with 2 or 3 variables per clause and at most 3 occurrences per variable.

[...]

Theorem 2.4. Every instance of r,r-SAT is satisfiable.

The reason there's no conflict is that you need to allow 2 or 3 literals per clause to make 3-SAT $NP$-complete when restricted to at most 3 occurrences per variable. The trivially satisfiable bit only kicks in when you have exactly 3 literals per clause and at most 3 occurrences per variable.

$\endgroup$
  • $\begingroup$ Ah ok, so in my last reference, for example, the definition of 3-SAT would have to be "instances with clauses of at most 3 literals" instead of "instances with exactly 3 literals" because the latter definition would lead to automatic satisfiability if each variable appears at most 3 times, right? $\endgroup$ – Paradox Oct 20 '15 at 4:56
  • $\begingroup$ What about 3 occurrences in total and no limit of literals in a clause? Is it also NP-Complete? $\endgroup$ – shinzou Jun 30 '17 at 12:13

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.