¿La completitud / dureza NP tiene que ser constructiva?

11

¿Hay alguna con las siguientes propiedades:LNP

  1. Se sabe que implica P = N P .LPP=NP

  2. No hay (conocido) tiempo polinómico reducción Turing de (o algún otro N P problema -Complete) a L .SATNPL

En otras palabras, si un algoritmo de tiempo polinomial para implica el colapso de N P en P , entonces es necesario que esta "dureza general" de L para N P sea ​​de alguna manera c o n s t r u c t i v e , en el sentido de que, digamos, S A T debe ser reducible a L mediante alguna reducción específica?LNPPLNPconstructiveSATL

Andras Farago
fuente
10
Me parece que el título y el cuerpo hacen dos preguntas diferentes. Por ejemplo, la respuesta de Kaveh funciona para la pregunta en el cuerpo, pero no para la pregunta en el título.
Robin Kothari

Respuestas:

15

Sí, existen tales conjuntos, tome cualquier conjunto intermedio (cualquier conjunto que sea demostrablemente N P- intermedio suponiendo PN P ), por ejemplo, construya uno de SAT usando el teorema de Ladner.NPNPPNP

Tenga en cuenta que su debe considerarse un problema intermedio N P , ya que está en N P pero no está completo. Tenga en cuenta también que usted está asumiendo que PN P de lo contrario no hay tal L como cada problema no trivial sería completa para N P si N P = P . Además, las condiciones que ha dado no implican integridad, por lo que la pregunta de la primera parte no es la misma que la pregunta sobre la constructividad de la integridad.LNPNPPNPLNPNP=P


En cuanto a la pregunta en el título, es decir, "¿la dureza tiene que ser constructiva?".NP

La respuesta depende de lo que entendemos por "constructivo". Clásicamente, un problema de decisión se define como N P -duro siANP

BNP BmPA

lo que significa

BNP fFP x{0,1} (xBf(x)A)

Y por el teorema de Cook esto es equivalente a

SATmPA

lo que significa

fFP x{0,1} (xSATf(x)A)

Af

Clásicamente, incluso cuando no tenemos una función específica, hay una función, decir que es imposible que ninguna función sea una reducción es equivalente a decir que alguna función es una reducción. Para hablar de constructividad, debemos ser más considerados. Por ejemplo, podemos hablar de enunciados que son demostrables de manera clásica pero no constructiva (por ejemplo, intuicionismo donde tiene sentido un estado diferente de conocimiento matemático, Google para "matemático ideal" o verifique esto ).

Intuitivamente me parece plausible que podamos probar tal afirmación usando una prueba por contradicción y sin dar ninguna función explícita de reducción. Pero no significará que no haya una prueba constructiva de la declaración. Para decir más que no existe una prueba constructiva, tenemos que ser más específicos: ¿pruebas en qué teoría / sistema? ¿Qué queremos decir con una prueba constructiva?

Kaveh
fuente
¿Por qué? ¿Un algoritmo de tiempo P para un problema intermedio implica P = NP?
Mohammad Al-Turkistany
1
NPPPNPNP
12

k

"Isomorphic" es diferente de una reducción de Turing (de hecho significativamente más débil), pero se demostró que estos conjuntos son NP-hard directamente y, hasta donde sé, no hay una reducción conocida de SAT. Dicho esto, según la definición de integridad de NP debe haber alguna reducción entre los dos, por lo que si bien cumple con el criterio de reducción "no conocida", puede que no sea exactamente lo que está buscando.

[1] Joseph, D. y Young, P. Algunas observaciones sobre funciones de testigos para conjuntos no polinómicos y no completos en NP. Informática teórica. vol 39, pág. 225--237. 1985. Elsevier.

SamM
fuente
6

El siguiente es un ejemplo de la pregunta en el título. Está tomado del siguiente documento: Jan Kratochvil, Petr Savicky y Zsolt Tuza. Una ocurrencia más de variables hace que la satisfacción salte de trivial a np-complete. SIAM Journal on Computing, 22 (1): 203–210, 1993.

Supongamos que f (k) es el entero máximo r de tal manera que cada foro k-SAT en el que cada variable se produce en la mayoría de las veces r, es satisfactoria. No se sabe si f (k) es computable, aunque se conocen límites relativamente estrechos para ello (véase H. Gebauer, R. Moser, D. Scheder y E. Welzl. El lema local y la satisfacción de Lov ́asz. Algoritmos eficientes, páginas 30–54, 2009.).

(k, s) -SAT es el problema k-SAT restringido a los forumlas en los que cada variable ocurre en la mayoría de los casos.

Kratochvil y col. demostró que (k, f (k) +1) -SAT es NP-completo. Tenga en cuenta que (k, f (k)): los problemas SAT siempre son satisfactorios (por definición). La reducción en sí misma no es constructiva: tenga en cuenta que la reducción genera una fórmula en la que cada variable ocurre como máximo f (k) +1 veces, aunque no se sabe que f (k) sea computable. La idea principal no constructiva es que aunque el valor f (k) es desconocido, existe una fórmula (k, f (k) +1) -SAT que no es satisfactoria, y manipulan esa fórmula de acuerdo con sus necesidades .

O sattath
fuente
2
kkf(k)
1
@Kaveh De hecho, la reducción no es computable, pero el problema en sí es: (k, s) -SAT está claramente en NP para cada s. El parámetro que hace que el problema NP-completo, es decir, f (k) +1, es el objeto que no es computable.
O Sattath
2

Agrawal y Biswas presentaron un lenguaje NP-completo para el cual no se conoce la reducción de Karp o Cook. La prueba de integridad se debe a que su relación de testigo es universal (la relación de testigo tiene la unión requerida y los operadores de equivalencia necesarios para ser universales). El lenguaje se da en la sección 6.3 de la referencia.

M.Agrawal, S.Biswas, Relaciones universales en procedimientos IEEE Conferenceon Structure in Complexity Theory (1992), pp. 207–220.

Mohammad Al-Turkistany
fuente
1
Un lenguaje NP-completo es, por definición, completo bajo las reducciones de Karp, entonces, ¿qué significa la primera oración?
Emil Jeřábek
@ EmilJeřábek Significa exactamente lo que dice, no se conoce la reducción de Karp o Cook. Agrawal y Biswas demostraron que los Conjuntos con relaciones universales son NP completos. Te sugiero que leas el periódico.
Mohammad Al-Turkistany
1
No, no puede significar lo que dice, porque lo que dice no tiene sentido. Algo que no se sabe que está completo bajo las reducciones de Karp es, a fortiori, no se sabe que NP-complete. Hojeé el resumen y la introducción del artículo, y todavía no encontré nada que coincidiera con su descripción.
Emil Jeřábek
@ EmilJeřábek Lea atentamente la sección 6.3. Me temo que el descremado no es suficiente en este caso :)
Mohammad Al-Turkistany
1
@ MohammadAl-Turkistany, creo que el punto es que las declaraciones "no se sabe que están completas bajo K. reducciones" y "no se conoce K. reducción" tienen significados diferentes. La publicación dice una cosa y tu comentario dice la otra.
usul