Recently, I am reading papers about dichotomy. I do not understant what condition can be called as a dichotomy? What is the meaning of "a question is either in P or in NP-complete"? (assume P $\neq$ NP)

For example, I've known the Schaefer's dichotomy theorem, in which a dichotomy about "whether a class of SAT is in P" is given. In this theorem, the dichotomy contains six conditions, one of them is "2-SAT".

So my question is that, whether "2-SAT" itself can be called as a dichotomy or a trivial dichotomy, because 2-SAT is in P but 3-SAT is NP-complete? In another words, I wonder that "if a special class of an NP-complete problem is in P, then this class is a dichotomy? or a trivial dichotomy?"

  • $\begingroup$ Yes, there's a dichotomy regarding $k$-SAT. As you say, the problem is in $P$ if and only if $k \leq 2$ (under usual complexity assumptions). $\endgroup$ – Pål GD Dec 11 '13 at 11:19

A (coarse) dichotomy theorem states that in a certain class of problems, each problem is either in P or NP-hard. For example, Schaefer's dichotomy theorem concerns the class of problems of the form $\mathrm{SAT}(S)$. Here $S$ is a collection of Boolean relations, and $\mathrm{SAT}(S)$ is the problem of deciding satisfiability of propositions which are conjunctions of relations from $S$. This is best explained by an example. The problem 2SAT is $\mathrm{SAT}(S_2)$ with $S_2$ consisting of the following three predicates: $$ (x,y) \mapsto x \lor y, \quad (x,y) \mapsto x \lor \lnot y, \quad (x,y) \mapsto \lnot x \lor \lnot y. $$ That is, each instance of 2SAT is a conjunctions of clauses of one of these three forms, where you can substitute any variables you want for $x,y$. As another example, HORNSAT is $\mathrm{SAT}(S_H)$ where $S_H$ is the following infinite collection: $$\begin{gather*} x \mapsto x, \quad x \mapsto \lnot x, \quad (x,y) \mapsto x \lor \lnot y, \quad (x,y) \mapsto \lnot x \lor \lnot y, \\ (x,y,z) \mapsto x \lor \lnot y \lor \lnot z, \quad (x,y,z) \mapsto \lnot x \lor \lnot y \lor \lnot z, \\ (x,y,z,w) \mapsto x \lor \lnot y \lor \lnot z \lor \lnot w, \quad (x,y,z,w) \mapsto \lnot x \lor \lnot y \lor \lnot z \lor \lnot w, \ldots \end{gather*}$$ Schaefer's dichotomy theorem states that for each finite $S$, the problem $\mathrm{SAT}(S)$ is either in P or it is NP-complete (this is a dichotomy since there are only two possibilities). For example, 2SAT and $k$-HORNSAT are in P for every $k$, while 3SAT is NP-complete. This is surprising since if we believe that P$\neq$NP then Ladner's theorem shows that there are intermediate problems - problems which are neither in P nor NP-complete. Schaefer's theorem shows that these problems cannot be of the form $\mathrm{SAT}(S)$.

A more refined version of Schaefer's theorem states that $\mathrm{SAT}(S)$ is either in co-NLOGTIME, L-complete, NL-complete, $\oplus$L-complete, P-complete or NP-complete. In the past few years, countless generalizations of Schaefer's theorem have been proven or conjectured, including results about counting solutions and approximating the maximum number of satisfiable clauses, as well as results over non-Boolean domains. The main conjecture is the Feder-Vardi dichotomy conjecture which states that Schaefer's theorem holds for relations on an arbitrary finite-sized domains. For the status of Schaefer's original theorem in the case where $S$ is infinite, see this question.

  • $\begingroup$ Thanks for your help, I got a little more clear, however, I am really confused about this question: whether "2-SAT" itself can be called as a dichotomy, because 2-SAT is in P but 3-SAT is NP-complete? In another words, I wonder that "if a special class of an NP-complete problem is in P, then this special class is a dichotomy? or a trivial dichotomy?" $\endgroup$ – Miao Dongjing Dec 11 '13 at 8:24
  • $\begingroup$ But what's the significance of a dichotomy ? $\endgroup$ – Miao Dongjing Dec 11 '13 at 8:38
  • 1
    $\begingroup$ 2SAT is not a dichotomy but a language. As you state, the dichotomy is that $\mathrm{SAT}(S)$ is either in P or NP-complete (at least for finite $S$). The significance is that there is this "gap" in complexity - every problem of type $\mathrm{SAT}(S)$ is either "easy" (in P) or "hard" (NP-complete), with nothing in between. This is surprising since we know that if P$\neq$NP then there must be problems whose complexity is intermediate (graph isomorphism could be one of them), but for some reason problems of the form $\mathrm{SAT}(S)$ never show this behaviour. $\endgroup$ – Yuval Filmus Dec 11 '13 at 8:48
  • $\begingroup$ While if remove one of the six conditions in the Schaefer's dichotomy theorem, is it still called a dichotomy? I think the important part is that "otherwise, it is in NP-complete", but he just want to give conditions as more as possible, right? $\endgroup$ – Miao Dongjing Dec 11 '13 at 9:01
  • $\begingroup$ I can't follow you. If you change Schaefer's theorem then you might get a statement which isn't true. $\endgroup$ – Yuval Filmus Dec 11 '13 at 16:56

The word "dichotomy" comes from the Greek dichotomia meaning divided, or split in two. Thus, a dichotomy is any statement of the form, "Everything is either A or B but not both." The classic example is, "You're either with us or against us." Schaeffer's dichotomy for Boolean CSP (which he calls "Generalized Satisfiability") is another example: for every finite set of Boolean relations, the corresponding satisfiability problem is either is either in P or is NP-complete (but not both, assuming that P$\neq$NP). Kuratowski's theorem is also a dichotomy: every graph is either planar of contains $K_5$ or $K_{3,3}$ as a (topological) minor.

Notice that a dichotomy isn't the end of the story and it might be possible to produce a more detailed classification. You might be completely with us or only slightly against us. Some of the polynomial-time cases of Schaeffer's theorem are easier than others (Allender, Bauland, Immerman, Schnoor, Voller, "The Complexity of Satisfiability Problems: Refining Schaeffer's Theorem". Journal of Computer and System Sciences, 75:245-254, 2009.)


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.