El teorema de Ladner contra el teorema de Schaefer

27

Mientras lee el artículo "¿Es hora de declarar la victoria en el conteo de la complejidad?" en el blog "La carta perdida de Godel y P = NP" , mencionaron la dicotomía para los CSP. Después de seguir algunos enlaces, buscar en Google y escribir en wikipedia, me encontré con el teorema de Ladner :

Teorema de Ladner: si , entonces hay problemas en N PP que no son N P -completos.PNPNPPNP

y al teorema de Schaefer :

Teorema de la dicotomía de Schaefer: para cada lenguaje de restricción Γ sobre { 0 , 1 } , si Γ es Schaefer, entonces C S P ( Γ ) tiene tiempo polinómico que se puede resolver. De lo contrario, C S P ( Γ ) es N P -completo. Γ{0,1} ΓCSP(Γ)CSP(Γ)NP

Leí esto para decir que, según Ladner, hay problemas que no son ni ni N P -completos, sino que, según Schaefer, los problemas son P y N P -completos solamente.PNPPNP

¿Qué me estoy perdiendo? ¿Por qué estos dos resultados no se contradicen?

Tomé la versión condensada de las declaraciones del teorema anterior de aquí . En su sección "Comentarios finales", dice "Por lo tanto, si un problema está en pero no es N P -Complete entonces no puede ser formulado como CSP".NPPNP

¿Significa esto que los problemas pierden algunas instancias que están en N P ? ¿Cómo es eso posible?SATNP

usuario834
fuente
2
¿No hay un pequeño problema en que uno debe tener cuidado de cómo se define "lenguaje de restricción" y "problema"? El teorema de Schaefers (hasta donde recuerdo), solo considera los idiomas dados tomando el cierre bajo conjunción y sustitución variable de algún conjunto S de relaciones. Sin embargo, uno puede construir conjuntos de problemas de restricciones que no están cubiertos por esto, por lo que puede ser manejable pero no Schaefer. Presumiblemente, el conjunto de problemas que construye Ladner simplemente no es definible en términos del cierre bajo la conjunción y la sustitución variable de un conjunto de relaciones.
MGwynne
1
SATCSP(Γ)

Respuestas:

15

Γ

(S,T)STST

ΓΓΓ{(S,T)all relations of T are from Γ}Γ{0,1}Γ) es NP-complete o en P, pero no dice nada sobre otras colecciones de instancias de CSP.

ΓΓΓ

András Salamon
fuente
23

CSPSATΓ={{(0,0),(1,1)},{(0,1),(1,0)}}. Este lenguaje es tal que solo puede expresar igualdad y desigualdad entre dos variables. Claramente, cualquier conjunto de restricciones de este tipo puede resolverse en tiempo polinómico.

CSPPNP

Γ

ΓORORORΓSATCSPΓ

ΓAND(1,1)OR(0,0)

SATCSPΓ

ΓNPPΓSAT

MassimoLauria
fuente
1
Para agregar a la excelente respuesta de MassimoLauria; No hay contradicción. Eche un vistazo a este artículo de Wikipedia que tiene una sección que explica, en palabras simples, la relación entre el teorema de Ladner y el teorema de Schaefer.
Mohammad Al-Turkistany
CSPSATCSP(Γ)SAT
ΓSATΓtHornSATpoly(t)CSP(es decir, exponencialmente muchas variables). ¿Tiene sentido?
MassimoLauria
Creo que la forma correcta de decirlo es que los CSP en el marco de Schaefer no pueden codificar un problema NP arbitrario (3-SAT es, de hecho, un problema de CSP canónico). Tenga en cuenta que esta es una declaración condicional (a menos que P = NP).
Chandra Chekuri
@ChandraChekuri, discúlpeme por ser tan denso, pero ¿está diciendo que los CSP en el marco de Schaefer no pueden codificar instancias arbitrarias de 3-SAT? CSP puede, en general, codificar 3-SAT, pero la versión restringida de CSP en el marco de Schaefer no puede?
usuario834