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.