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 P ∖ P que no son N P -completos.
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.
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.
¿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".
¿Significa esto que los problemas pierden algunas instancias que están en N P ? ¿Cómo es eso posible?
fuente
Respuestas:
fuente
fuente