[Solved]: What is a dichotomy? Whether 2-SAT itself is a dichotomy of SAT?

Problem Detail: 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 NPcomplete“? (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 NPcomplete? In another words, I wonder that “if a special class of an NPcomplete problem is in P, then this class is a dichotomy? or a trivial dichotomy?”

Asked By : Miao Dongjing

Answered By : Yuval Filmus

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.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18865

Leave a Reply