# Which subproblems of 3SAT are still NP complete?

The $\mathsf{NP}$-complete problems satisfy the property that if any of them is in $\mathsf{P}$, then all other $\mathsf{NP}$-complete problems are in $\mathsf{P}$. The problem $3$-SAT is $\mathsf{NP}$-complete, as much as every $k$-SAT with $k\geq 3$. (On the other hand, $2$-SAT is known to be in $\mathsf{P}$).

Obviously, the problem $3$-SAT can be seen as a subset of $k$-SAT for $k\geq 3$ and, in general, all of them are a subclass of SAT.

However my question goes in the opposite direction: which are some smaller subclasses of $3$-SAT that are still $\mathsf{NP}$-complete?

I am interested in studying the $\mathsf{P} = \mathsf{NP}$ conjecture by looking just into smaller class of $3$-SAT problems that are still acceptable.

• I don't think you're going to find a unique answer to this question. There are many ways to define small subclasses of 3SAT that remain NP-complete, and these different answers are going to be incomparable. – D.W. Aug 30 '13 at 7:24
• I asked a similar question on cs.stackexchange.com, perhaps Juho's answer can help you. – Marzio De Biasi Aug 30 '13 at 7:55
• @D.W. I know that, but I don't know how to write the question in a better way. I need information about small subclasses of 3SAT. – pablo1977 Aug 30 '13 at 14:25
• I think Juho's answer on cs.stackexchange.com is the definitive one. @MarzioDeBiasi maybe you can post an answer that points to that link, and the OP can accept it. – Suresh Venkat Aug 31 '13 at 0:05

One can restrict $3$-SAT by allowing only a certain number of occurrences of every variable.

If $3$-CNF means that every clause contains at most $3$ variables, then satisfiability of $3$-CNF fomulas remains $\mathsf{NP}$-complete for formulas where every variable has at most 3 occurrences.

If $3$-CNF means that every clause contains exactly $3$ variables, then the answer is slightly different:

• for formulas where every variable has at most 3 occurrences satisfiablility is in $\mathsf{P}$ - in fact it is trivial, every such formula is satisfiable.
• for formulas where every variable has at most 4 occurrences, satisfiability is $\mathsf{NP}$-complete.
• Very useful and clear answer. Thank you very much. – pablo1977 Apr 16 '15 at 15:37
• This is very interesting. Thank you! :) – Michael Wehar Apr 16 '15 at 20:19

I asked a similar question on cs.stackexchange.com, perhaps Juho's answer can help you; it contains references to: MONOTONE NAE-3SAT, MONOTONE 1-in-3-SAT, PLANAR 3SAT, k-COLOURABLE MONOTONE NAE-3SAT.

You can find other variants also in this cstheory question: 4-BOUNDED PLANAR 3-CONNECTED 3SAT, POSITIVE PLANAR 1-in-3 SAT.

there are many answers to this cited elsewhere, here is one additional one that maybe captures the boundary between P/NP in a natural way and fittingly along the lines requested. a distinctive/ interesting model is the $(2+p)$-SAT model for $0 \leq p \leq 1$ inspired by research relating to phase transitions and statistical mechanics. the idea is that instances have a count of 2-width and 3-width clauses in a mixture wrt the $p$ ratio. two papers: