O que é uma dicotomia? Se o 2-SAT em si é uma dicotomia do SAT?

Recentemente, estou lendo artigos sobre dicotomia . Não entendo que condição pode ser chamada de dicotomia ? Qual é o significado de "uma pergunta está em P ou em NP - completa "? (suponha P NP )$\neq$

Por exemplo, eu conheço o teorema da dicotomia de Schaefer, no qual é dada uma dicotomia sobre "se uma classe de SAT está em P ". Nesse teorema, a dicotomia contém seis condições, uma delas é "2-SAT".

Então, minha pergunta é: se o próprio 2-SAT pode ser chamado de dicotomia ou dicotomia trivial , porque o 2-SAT está em P, mas o 3-SAT é NP - completo ? Em outras palavras, eu quero saber que "se uma classe especial de um NP - completa problema está em P , então essa classe é uma dicotomia ou uma dicotomia trivial?"

Um teorema da dicotomia (grosseira) afirma que, em uma certa classe de problemas, cada problema é difícil ou P ou NP. Por exemplo, o teorema da dicotomia de Schaefer diz respeito à classe de problemas da forma . Aqui é um conjunto de relações booleanas, e é o problema de decidir satisfiability de proposições que são conjunções de relações de . Isso é melhor explicado por um exemplo. O problema 2SAT é com consiste nos três predicados a seguir: $\mathrm{SAT}(S)$$S$$\mathrm{SAT}(S)$$S$$\mathrm{SAT}(S_2)$$S_2$

$$(x,y) \mapsto x \lor y, \quad (x,y) \mapsto x \lor \lnot y, \quad (x,y) \mapsto \lnot x \lor \lnot y.$$ Ou seja, cada instância do 2SAT é uma conjunção de cláusulas de uma dessas três formas, onde é possível substituir as variáveis ​​desejadas por . Como outro exemplo, HORNSAT é que é a seguinte coleção infinita: o teorema da dicotomia de Schaefer afirma que, para cada finito$x,y$$\mathrm{SAT}(S_H)$$S_H$ $$\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*}$$ $S$ , o problema está em P ou está completo em NP (esta é uma dicotomia, pois existem apenas duas possibilidades). Por exemplo, 2SAT e -HORNSAT estão em P para cada , enquanto 3SAT é NP-completo. Isso é surpreendente, pois se acreditarmos que P NP, o teorema de Ladner mostra que existem problemas intermediários - problemas que não estão nem em P nem em NP completos. O teorema de Schaefer mostra que esses problemas não podem ter a forma .$\mathrm{SAT}(S)$$k$$k$$\neq$$\mathrm{SAT}(S)$

Uma versão mais refinada do teorema de Schaefer afirma que está co-NLOGTIME, L-completo, NL-completo, L-completo, P-completo ou NP-completo. Nos últimos anos, inúmeras generalizações do teorema de Schaefer foram comprovadas ou conjecturadas, incluindo resultados sobre soluções de contagem e aproximação do número máximo de cláusulas satisfatórias, além de resultados sobre domínios não-booleanos. A conjetura principal é a conjetura de dicotomia Feder-Vardi, que afirma que o teorema de Schaefer vale para relações em domínios arbitrários de tamanho finito. Para o status do teorema original de Schaefer no caso em que é infinito, veja esta pergunta .$\mathrm{SAT}(S)$$\oplus$$S$

A palavra "dicotomia" vem do grego dicotomia, que significa dividido ou dividido em dois. Assim, uma dicotomia é qualquer afirmação da forma "Tudo é A ou B, mas não ambos". O exemplo clássico é: "Você está conosco ou contra nós". A dicotomia de Schaeffer para CSP booleano (que ele chama de "satisfação generalizada") é outro exemplo: para todo conjunto finito de relações booleanas, o problema de satisfação correspondente é em P ou em NP-completo (mas não em ambos, assumindo que P NP). O teorema de Kuratowski também é uma dicotomia: todo gráfico é planar ou contém ou como um menor (topológico).$\neq$$K_5$$K_{3,3}$

Observe que uma dicotomia não é o fim da história e pode ser possível produzir uma classificação mais detalhada. Você pode estar completamente conosco ou apenas ligeiramente contra nós. Alguns dos casos de tempo polinomial do teorema de Schaeffer são mais fáceis do que outros (Allender, Bauland, Immerman, Schnoor, Voller, "A complexidade dos problemas de satisfação: refinando o teorema de Schaeffer" . Journal of Computer and System Sciences , 75: 245-254, 2009.)