¿El NPI está contenido en P / poli?

29

Se conjetura que ya que lo contrario implicaría \ mathsf {PH} = \ Sigma_2 . El teorema de Ladner establece que si \ mathsf {P} \ ne \ mathsf {NP} entonces \ mathsf {NPI}: = \ mathsf {NP} \ setminus (\ mathsf {NPC} \ cup \ mathsf {P}) \ ne \ emptyset . Sin embargo, la prueba no parece generalizarse a \ mathsf {P} / \ text {poly}, por lo que la posibilidad \ mathsf {NPI} \ subset \ mathsf {P} / \ text {poly} es decir \ mathsf {NP} \ El subconjunto \ mathsf {NPC} \ cup \ mathsf {P} / \ text {poly} parece estar abierto.NPP/polyPN P N P I : = N P( N P CP ) P / poly N P IP / poly N PN P CP / polyPH=Σ2PNPNPI:=NP(NPCP)P/polyNPIP/polyNPNPCP/poly

Suponiendo que NPP/poly (o incluso que la jerarquía polinómica no colapsa en ningún nivel), es NPIP/poly sabe que el texto {poly} es verdadero o falso? ¿Qué evidencia se puede poner a favor y en contra?

Vanessa
fuente
55
entonces, "¿qué pasaría si todos los problemas en NP son NP completos o en P \ poly"? por un lado, implicaría pequeños circuitos para factoraje
Sasho Nikolov
1
ps: la publicación sería más fácil de leer si deletrea "eso" en la parte citada. También es posible que desee utilizar NPP/poly en lugar de NPP como su suposición.
Kaveh
44
¿No mostrará un argumento de relleno que esto no puede suceder a menos que NP P / poly?
Peter Shor
3
@ PeterShor: Probablemente estoy siendo denso, pero ¿cómo funcionaría exactamente?
Vanessa
8
@Squark: no estás siendo denso ... No había trabajado exactamente cómo funcionaría, y creo que expresé mal el resultado ligeramente. Pero aquí está mi idea básica. Suponga que los problemas de NP completo no pueden resolverse en tiempo y consejos subexponenciales. Tome un problema NP-completo X, y acomódelo de modo que el algoritmo más rápido para él sea apenas subexponencial. Entonces es NPI, por lo que se puede resolver en P / poly. Esto significa que el problema NP-completo X puede resolverse a tiempo solo un poco más lento que el tiempo P / poli. Por reducción polinómica, ahora todos los problemas de NP completo se pueden resolver en un tiempo ligeramente más lento que el tiempo P / poli.
Peter Shor

Respuestas:

18

Aquí hay una posible alternativa a un argumento de relleno, basado en la generalización de Schöning del teorema de Ladner. Para comprender el argumento, debe tener acceso a este documento (que desafortunadamente estará detrás de un muro de pago para muchos):

Uwe Schöning. Un enfoque uniforme para obtener conjuntos diagonales en clases de complejidad. Informática teórica 18 (1): 95-103, 1982.

Vamos a aplicar el teorema principal de ese papel para y siendo idiomas y y siendo clases de la complejidad de la siguiente manera:A 2 C 1 C 2A1A2C1C2

  • PA1= (o cualquier idioma en )P
  • A2=SAT
  • C1=NPC
  • C2=NPP/poly

En aras de la claridad, el hecho que demostraremos es implica .N P IP / p o l yNPP/polyNPIP/poly

Bajo el supuesto de que tenemos y . Está claro que y están cerrados bajo variaciones finitas. El artículo de Schöning incluye una prueba de que es presentable de forma recursiva (la definición precisa de lo cual se puede encontrar en el documento), y la parte más difícil del argumento es demostrar que es presentable de forma recursiva.A 1C 1 A 2C 2 C 1 C 2 C 1 C 2NPP/polyA1C1A2C2C1C2C1C2

Bajo estos supuestos, el teorema implica que existe un lenguaje que no está ni en ni en ; y dado que , sostiene que es Karp-reducible a , y por lo tanto . Dado que está en pero no es -completo ni en , se deduce que .C 1 C 2 A 1P A A 2 A N P A N P N P N PP / p o l y N P IP / p o l yAC1C2A1PAA2ANPANPNPNPP/polyNPIP/poly

Queda por demostrar que es presentable de forma recursiva. Básicamente, esto significa que hay una descripción explícita de una secuencia de máquinas Turing deterministas que se detienen en todas las entradas y son tales que . Si hay un error en mi argumento, probablemente esté aquí, y si realmente necesita usar este resultado, querrá hacerlo con cuidado. De todos modos, al encajar en todas las máquinas de Turing no deterministas de tiempo polinómico (que se pueden simular determinísticamente porque no nos importa el tiempo de ejecución de cadaM 1 , M 2 , N PP / p o l y = { L ( M k ) : k = 1 , 2 , } M k M k M kNPP/polyM1,M2,NPP/poly={L(Mk):k=1,2,}Mk) y todos los polinomios, que representan límites superiores en el tamaño de una familia de circuitos booleanos para un idioma determinado, creo que no es difícil obtener una enumeración que funcione. En esencia, cada puede probar que su NTM de tiempo polinomial correspondiente concuerda con alguna familia de circuitos de tamaño polinómico hasta la longitud de la cadena de entrada que se le da buscando en todos los circuitos booleanos posibles. Si hay acuerdo, como lo haría la NTM, de lo contrario, rechaza (y como resultado representa un lenguaje finito).MkMk

La intuición básica detrás del argumento (que está oculto dentro del resultado de Schöning) es que nunca se pueden tener dos clases de complejidad "agradables" (es decir, las que tienen presentaciones recursivas) que son disjuntas y están juntas. La "topología" de las clases complejas no lo permite: siempre se puede construir un lenguaje correctamente entre las dos clases alternando de alguna manera entre las dos para tramos extremadamente largos de longitudes de entrada. El teorema de Ladner muestra esto para y , y la generalización de Schöning le permite hacer lo mismo para muchas otras clases.N P CPNPC

John Watrous
fuente
77
Este es un enlace a las publicaciones de Schöning disponibles en línea de forma gratuita, incluida la que usted menciona: uni-ulm.de/in/theo/m/schoening/…
Alessandro Cosentino
1
¡Muchas gracias por tu respuesta! Lo curioso es que conocía el teorema de Shoening, pero por alguna tonta razón pensé que no se aplica en este caso. Por cierto, el texto está disponible gratuitamente incluso en sciencedirect
Vanessa
1
@Squark: no es tonto sospechar que el teorema de Schöning no se aplica, dado que P / poly incluye lenguajes no recursivos. Supongo que es una buena suerte que podamos cruzarlo con NP y aún así obtener el resultado.
John Watrous
1
@ JohnWatrous: Sí, esta es precisamente la razón por la que estaba confundida
Vanessa
15

Solo me gustaría escribir alguna versión de un argumento de relleno como se describe en los comentarios. No veo por qué se necesita una brecha. Queremos mostrar que si NP no está contenido en P / poly, entonces hay un problema NP-intermedio no contenido en P / poly.

Hay una función ilimitada tal que SAT no tiene circuitos de tamaño menor que , por lo que hay una función que no está limitada, aumenta y . Deje que SAT 'denote el lenguaje obtenido al rellenar cadenas SAT de longitud a . Luego:n f ( n ) g g ( n ) = o ( f ( n ) ) n n g ( n )fnf(n)gg(n)=o(f(n))nng(n)

  • SAT 'está en NP (ver más abajo)
  • SAT 'no está en P / poli: dados los circuitos de tamaño para SAT', obtenemos circuitos de tamaño para SAT, pero esto es menor que para algunos .n g ( n ) k n f ( n ) nnkng(n)knf(n)n
  • No hay reducción de P / poli de SAT a SAT ': suponga por contradicción que hay circuitos de tamaño para SAT, permitiendo puertas SAT'. Escoja suficientemente grande que y dejar que . Cada compuerta SAT 'en tiene como máximo entradas. Al eliminar las entradas de relleno, podemos recortar las compuertas SAT 'en a una compuerta SAT con menos de entradas, que podemos simular usando : las compuertas SAT' resultantes tienen como máximo entradas. Repitiendo esto y tratando a mano, SAT tendría circuitos de aproximadamente el tamañon k N g ( CnnkNn>NCnnkCng(N)>2kn>NCnnkCn CnCnnk/2CNO(nknk/2nk/4)O(n2k) que es menor que para algunos .nf(n)n

Editar:

La elección de es ligeramente complicada. Si está contento de poner SAT 'en la versión prometedora de NP, este bit es innecesario.g

Defina como el número entero máximo de manera que no exista un circuito de tamaño para la longitud cadenas para SAT. Defina mediante un algoritmo que calcula para y se detiene después del tiempo o cuando , y devuelve el piso de la raíz cuadrada del valor más alto encontrado en este tiempo . Entonces no tiene límites y y se puede calcular en el tiempo . Ahora tenga en cuenta que los argumentos anteriores solo se basan en que SAT no tiene circuitos de tamaño para infinitamentef(n)nf(n)ng(n)f(m)m=1,2,nm=ng(n)lim infg(n)/f(n)=0g(n)nnf(n)n.

También me parece interesante ver una prueba haciendo agujeros en SAT como en http://blog.computationalcomplexity.org/media/ladner.pdf . Sin el requisito de NP, esto es bastante fácil: hay una secuencia tal manera que ningún tamaño de circuito os detecta cadenas SAT de longitud ; restringir SAT a cadenas de longitud para algunos .( n k ) k n n 2 2 i in1<n2<(nk)knn22ii

Colin McQuillan
fuente
1
Después de ver la respuesta de @ JohnWatrous, me acordé de la prueba de Impagliazzo del Teorema de Ladner mediante el relleno (véase el apéndice de Downey y Fortnow "Uniformly Hard Languages": cs.uchicago.edu/~fortnow/papers/uniform.pdf ). De hecho, su prueba es básicamente la prueba de Impagliazzo de Ladner, pero adaptada a esta situación. ¡Ordenado!
Joshua Grochow
1
¡Muchas gracias por tu respuesta! Me disculpo por no haberlo seleccionado, pero tuve que elegir uno y el argumento de Watrous fue más fácil de seguir, ya que utilizó un resultado que ya conocía. Esta es una forma bastante subjetiva de elegir, pero no podría hacerlo mejor. De todos modos, es genial tener más de una forma de llegar a un resultado interesante
Vanessa,
1
@Squark: absolutamente, y también asumí que el teorema de Schöning no se aplicaba.
Colin McQuillan
-13

(NPI P / poly) (P NP)

vzn
fuente
8
es conocido y trivial: si P = NP, entonces . Además, esta no es la pregunta, la pregunta es lo contrario de lo que escribiste, y Colin respondió convincentemente hasta donde puedo ver. NPINP=PP/pol
Sasho Nikolov
la pregunta se titula "está NPI contenido en P / Poly" y creo que esta es una respuesta razonable, no estoy seguro de que sea realmente trivial debido a la forma en que generalmente se define NPI (como dependiente de P NP) ... esta respuesta no conflicto con la otra respuesta ...
vzn
9
En realidad, es aún más obviamente trivial: si P = NP, NPI está vacío. La pregunta se establece claramente como "NP no contenido en P / poly implica NPI no en P / poly. Entonces su respuesta 1) afirma que un hecho trivial es un problema abierto 2) no aborda la pregunta
Sasho Nikolov
8
No podría importarme menos los puntos. Por última vez: mi primer comentario, la respuesta de Colin, y la pregunta en sí están relacionadas con la conversación mucho menos trivial y más interesante de la implicación vacía que anotó.
Sasho Nikolov
11
-1: a veces perder el punto se siente bien
Alessandro Cosentino