¿Qué es una dicotomía? ¿Si 2-SAT en sí es una dicotomía de SAT?

Recientemente, estoy leyendo documentos sobre dicotomía . No entiendo qué condición se puede llamar como una dicotomía ? ¿Cuál es el significado de "una pregunta está en P o en NP - completa "? (suponga P $\neq$ NP )

Por ejemplo, conozco el teorema de la dicotomía de Schaefer, en el que se da una dicotomía sobre "si una clase de SAT está en P ". En este teorema, la dicotomía contiene seis condiciones, una de ellas es "2-SAT".

Entonces, mi pregunta es si "2-SAT" en sí puede llamarse como una dicotomía o una dicotomía trivial , porque 2-SAT está en P pero 3-SAT es NP - ¿ completo ? En otras palabras, me pregunto que "si una clase especial de un problema NP - completo está en P , entonces esta clase es una dicotomía o una dicotomía trivial".

Un teorema de dicotomía (grueso) establece que en una cierta clase de problemas, cada problema está en P o NP-duro. Por ejemplo, el teorema de dicotomía de Schaefer se refiere a la clase de problemas de la forma$\mathrm{SAT}(S)$. aquí$S$ es una colección de relaciones booleanas, y $\mathrm{SAT}(S)$ es el problema de decidir la satisfacción de las proposiciones que son conjunciones de relaciones de $S$. Esto se explica mejor con un ejemplo. El problema 2SAT es$\mathrm{SAT}(S_2)$ con $S_2$ que consta de los siguientes tres predicados:

$$(x,y) \mapsto x \lor y, \quad (x,y) \mapsto x \lor \lnot y, \quad (x,y) \mapsto \lnot x \lor \lnot y.$$ Es decir, cada instancia de 2SAT es una conjunción de cláusulas de una de estas tres formas, donde puede sustituir cualquier variable que desee $x,y$. Como otro ejemplo, HORNSAT es$\mathrm{SAT}(S_H)$ dónde $S_H$ es la siguiente colección infinita: $$\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*}$$ El teorema de dicotomía de Schaefer establece que para cada finito $S$, el problema $\mathrm{SAT}(S)$está en P o NP-completo (esto es una dicotomía ya que solo hay dos posibilidades). Por ejemplo, 2SAT y$k$-HORNSAT están en P por cada $k$, mientras que 3SAT es NP-completo. Esto es sorprendente ya que si creemos que P$\neq$NP, entonces el teorema de Ladner muestra que hay problemas intermedios, problemas que no están ni en P ni en NP completos. El teorema de Schaefer muestra que estos problemas no pueden ser de la forma$\mathrm{SAT}(S)$.

Una versión más refinada del teorema de Schaefer establece que $\mathrm{SAT}(S)$ está en co-NLOGTIME, L-complete, NL-complete, $\oplus$L-completo, P-completo o NP-completo. En los últimos años, se han probado o conjeturado innumerables generalizaciones del teorema de Schaefer, incluidos los resultados sobre el conteo de soluciones y la aproximación del número máximo de cláusulas satisfactorias, así como los resultados sobre dominios no booleanos. La conjetura principal es la conjetura de la dicotomía de Feder-Vardi que establece que el teorema de Schaefer es válido para las relaciones en dominios arbitrarios de tamaño finito. Para el estado del teorema original de Schaefer en el caso donde$S$es infinito, mira esta pregunta .

La palabra "dicotomía" proviene del griego dicotomía que significa dividido, o dividido en dos. Por lo tanto, una dicotomía es cualquier declaración de la forma, "Todo es A o B pero no ambos". El ejemplo clásico es: "Estás con nosotros o contra nosotros". La dicotomía de Schaeffer para CSP booleana (que él llama "Satisfacción generalizada") es otro ejemplo: para cada conjunto finito de relaciones booleanas, el problema de satisfacción correspondiente está en P o está completo en NP (pero no en ambos, suponiendo que P$\neq$NOTARIO PÚBLICO). El teorema de Kuratowski también es una dicotomía: cada gráfico es plano o contiene$K_5$ o $K_{3,3}$ como un menor (topológico).

Tenga en cuenta que una dicotomía no es el final de la historia y podría ser posible producir una clasificación más detallada. Puede estar completamente con nosotros o solo un poco en contra de nosotros. Algunos de los casos de tiempo polinomial del teorema de Schaeffer son más fáciles que otros (Allender, Bauland, Immerman, Schnoor, Voller, "The Complexity of Satisfiability Problems: Refining's Soreffer's Theorem" . Journal of Computer and System Sciences , 75: 245-254, 2009.)