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

<p>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. </p>

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

<ul>
<li>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. </li>
<li>for formulas where every variable has at most 4 occurrences, satisfiability is $\mathsf{NP}$-complete.</li>
</ul>

CC BY-SA 3.0
2015-04-16T15:37:22.487Z
Very useful and clear answer. Thank you very much.
pablo1977
CC BY-SA 3.0
2015-04-16T20:19:00.533Z
This is very interesting.  Thank you!  :)
Michael Wehar
CC BY-SA 3.0
2015-04-16T13:52:56.990Z
2015-04-16T13:52:56.990Z
Jan Johannsen
<p>I asked a <a href="https://cs.stackexchange.com/a/1235/140">similar question on cs.stackexchange.com</a>, 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.</p>

<p>You can find other variants also in this <a href="https://cstheory.stackexchange.com/questions/18899/variations-of-sat">cstheory question</a>: 4-BOUNDED PLANAR 3-CONNECTED 3SAT, POSITIVE PLANAR 1-in-3 SAT.</p>

CC BY-SA 3.0
2015-04-16T07:01:41.417Z
2015-04-16T07:01:41.417Z
2017-04-13T12:48:30.830Z
Marzio De Biasi
<p>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:</p>

<ul>
<li><p><a href="https://users.soe.ucsc.edu/~optas/papers/2psat.pdf" rel="nofollow">Rigorous results for random (2 + p)-SAT</a> / Achlioptas, Kirousis, Kranakis, Krizanc</p></li>
<li><p><a href="http://www.cs.cornell.edu/selman/papers/pdf/99.random.typical.pdf" rel="nofollow">2+ P-SAT: Relation of Typical-Case Complexity to the Nature of the Phase Transition</a> / Monasson, Zecchina, Kirkpatrick, Selman, Troyansky</p></li>
</ul>

CC BY-SA 3.0
2015-04-16T02:38:02.170Z
2015-04-16T02:38:02.170Z
vzn
<p>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}$).</p>

<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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2013-08-30T07:24:47.880Z
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.
CC BY-SA 3.0
2013-08-30T07:55:09.450Z
I asked a similar [question](http://cs.stackexchange.com/questions/1234/classification-of-intractable-tractable-satisfiability-problem-variants) on cs.stackexchange.com, perhaps Juho's answer can help you.
Marzio De Biasi
CC BY-SA 3.0
2013-08-30T14:25:33.007Z
@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
CC BY-SA 3.0
2013-08-31T00:05:11.863Z
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
<complexity-classes><sat>
Which subproblems of 3SAT are still NP complete?
pablo1977
# Which subproblems of 3SAT are still NP complete?

(Asked by: username_0 on 2013-08-30)

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.

**Tags:** complexity-classes, sat
> **Comments:**
> **username_1**: 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.  
> **username_2**: I asked a similar [question](http://cs.stackexchange.com/questions/1234/classification-of-intractable-tractable-satisfiability-problem-variants) on cs.stackexchange.com, perhaps Juho's answer can help you.  
> **username_0**: @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.  
> **username_3**: 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.  

---

## 3 answers

### Answer by username_4 on 2015-04-16. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: Very useful and clear answer. Thank you very much.  
> **username_5**: This is very interesting.  Thank you!  :)  

---

### Answer by username_2 on 2015-04-16. Score: 10

I asked a [similar question on cs.stackexchange.com](https://cs.stackexchange.com/a/1235/140), 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](https://cstheory.stackexchange.com/questions/18899/variations-of-sat): 4-BOUNDED PLANAR 3-CONNECTED 3SAT, POSITIVE PLANAR 1-in-3 SAT.


---

### Answer by username_6 on 2015-04-16. Score: -1

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:

* [Rigorous results for random (2 + p)-SAT](https://users.soe.ucsc.edu/~optas/papers/2psat.pdf) / Achlioptas, Kirousis, Kranakis, Krizanc
* [2+ P-SAT: Relation of Typical-Case Complexity to the Nature of the Phase Transition](http://www.cs.cornell.edu/selman/papers/pdf/99.random.typical.pdf) / Monasson, Zecchina, Kirkpatrick, Selman, Troyansky


---

