5
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Aug 30 '13 at 7:24
  • 7
    $\begingroup$ I asked a similar question on cs.stackexchange.com, perhaps Juho's answer can help you. $\endgroup$ – Marzio De Biasi Aug 30 '13 at 7:55
  • $\begingroup$ @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. $\endgroup$ – pablo1977 Aug 30 '13 at 14:25
  • 7
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Aug 31 '13 at 0:05
5
$\begingroup$

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.
Improve this answer
$\endgroup$
  • $\begingroup$ Very useful and clear answer. Thank you very much. $\endgroup$ – pablo1977 Apr 16 '15 at 15:37
  • $\begingroup$ This is very interesting. Thank you! :) $\endgroup$ – Michael Wehar Apr 16 '15 at 20:19
10
$\begingroup$

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.

Improve this answer
$\endgroup$
-1
$\begingroup$

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:

Improve this answer
$\endgroup$

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.