# 3-SAT for variables appearing 3 times

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:

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

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.

• 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). – Juho Oct 19 '15 at 14:40

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.

• 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? – Paradox Oct 20 '15 at 4:56
• What about 3 occurrences in total and no limit of literals in a clause? Is it also NP-Complete? – shinzou Jun 30 '17 at 12:13