Un problema de decisión que no se sabe que está en PH pero estará en P si P = NP

28

Editar : como Ravi Boppana señaló correctamente en su respuesta y Scott Aaronson también agregó otro ejemplo en su respuesta , la respuesta a esta pregunta resultó ser "sí" de una manera que no esperaba en absoluto. Primero pensé que no respondían la pregunta que quería hacer, pero después de pensarlo, estas construcciones responden al menos a una de las preguntas que quería hacer, es decir, "¿Hay alguna forma de probar un resultado condicional? P = NP ⇒ L ∈P 'sin probar el resultado incondicional L ∈PH? ”¡Gracias, Ravi y Scott!


¿Existe un problema de decisión L tal que se cumplan las siguientes condiciones?

  • No se sabe que L esté en la jerarquía polinómica.
  • Se sabe que P = NP implicará L ∈P.

Un ejemplo artificial es tan bueno como uno natural. Además, aunque uso la letra " L ", puede ser un problema prometedor en lugar de un idioma si ayuda.

Antecedentes . Si sabemos que un problema de decisión L está en la jerarquía polinómica, entonces sabemos que "P = NP ⇒ L ∈P". La intención de la pregunta es preguntar si lo inverso es válido. Si existe un lenguaje L que satisfaga las dos condiciones anteriores, entonces puede considerarse como una evidencia de que lo contrario falla.

La pregunta ha sido motivada por el interesante comentario de Joe Fitzsimons a mi respuesta a la pregunta de Walter Bishop " Consecuencias de #P = FP ".

Tsuyoshi Ito
fuente
Probar un negativo universal siempre es difícil (er), pero me sorprendería que tal lenguaje existiera. La conjetura generalizada de Linial-Nisan (si hubiera resultado cierta) no habría implicado lo que estás preguntando, no lo creo. Simplemente habría significado que BQP no estaba contenido en PH. Si el PH colapsó a P, BQP aún no habría estado contenido en P (H).
Daniel Apon
¿Está preguntando si existe una clase de complejidad X st X no es un subconjunto de PH y P = NP -> X = P?
Philip White
@Philip: Sí, pero no creo que eso cambie el problema porque generalmente podemos convertir un problema de decisión L en una clase X de problemas de decisión reducible a L. Al menos esa fue mi intención de hacer esta pregunta en términos de problemas de decisión .
Tsuyoshi Ito
¿Quizás desee exigir que el idioma esté de alguna manera cerca del PH, además de sus requisitos actuales? Tal vez, digamos, en PSPACE (aunque es discutible lo cerca que está PSPACE de PH; ver S. Fenner, S. Homer, M. Schaefer, R. Pruim. Jerarquías hiperpolinomiales y el salto polinomial. Informática teórica. Volumen 262 ( 2001), pp. 241-256 cse.sc.edu/~fenner/papers/hyp.pdf ). O tal vez realmente quieras pedir un lenguaje natural de este tipo. L
Joshua Grochow
@ Joshua: Gracias por el comentario y la referencia. Como se indicó en la actualización (revisión 3), ahora creo que hice la pregunta correcta (contrario a lo que agregué en la revisión 2). Quería saber "¿Hay alguna forma de probar un resultado condicional 'P = NP ⇒ L∈P' sin probar el resultado incondicional L∈PH?" Para este propósito, la naturalidad del problema no debería ser necesaria porque una vez allí es un método de prueba, debe aplicarse igualmente a los ejemplos naturales y artificiales.
Tsuyoshi Ito

Respuestas:

26

Como no le importa un lenguaje artificial, ¿qué le parece definir que esté vacío si P es igual a NP y ser el problema de detención si P no es igual a NP? De acuerdo, es un poco tramposo, pero creo que tendrás que reformular el problema para evitar tales tramposos. L

Ravi Boppana
fuente
55
Gracias, veo el punto (defina L = {M: la máquina de Turing M se detiene y P ≠ NP}). Por supuesto, esto no responde a lo que quería preguntar, pero supongo que tengo que pensar más para formular la pregunta que quería hacer correctamente.
Tsuyoshi Ito
30

Si un ejemplo artificial es realmente tan bueno como uno natural, ¡entonces sí puedo dar ese ejemplo!

Editar: Además, mi ejemplo es "algo" menos engañoso que el sugerido por Ravi Boppana (donde tomamos L como el idioma vacío si P = NP y el problema de detención de lo contrario), en eso definiré el idioma L dando un procedimiento finito para decidir si L para cualquier entrada x. En ningún momento se decidirá si x∈L requiere resolver una pregunta matemática "ilimitada" como P vs. NP.x


Sin más preámbulos: dejar que ser una enumeración de máquinas Polytime Turing. Para todo n , sea M t ( n ) el primer lexicográfico M i que decida correctamente 3SAT en todas las entradas de longitud n o menos. Luego defina el lenguaje L de la siguiente manera: para todas las entradas x de tamaño n , x L si y solo si la máquina de Turing codificada por x se detiene como máximo n t ( n )M1,M2,...nMt(n)Minxnxxnt(n) pasos cuando se ejecuta en una cinta en blanco.

Reclamación 1: Si P = NP, entonces L P.

Prueba: si P = NP, entonces hay algo de fijo que resuelve 3SAT para todas las entradas; por lo tanto t ( n ) i para todo n . QEDMit(n)in

Reclamación 2: si P NP, entonces L P.

Prueba: si aumenta sin límite, entonces simplemente podemos aplicar el Teorema de la Jerarquía de Tiempo. QEDt(n)

Ahora, no solo L no está en P suponiendo P NP: ¡se supone que tampoco estaría en PH (o incluso PSPACE)!

Por cierto, me pregunto si alguien puede mejorar la construcción anterior, para obtener un lenguaje L que está en P si P = NP, pero probablemente no en PH o PSPACE si P NP?

Scott Aaronson
fuente
1
¡Gracias! No he podido modificar la construcción para que la no pertenencia a PH sea demostrable, pero esto es suficiente para convencerme de que agregar la condición de que L es decidible con una prueba constructiva de la capacidad de decisión probablemente no cambiará mucho la situación. Hmm
Tsuyoshi Ito
3
Aceptaré la respuesta de Ravi Boppana porque fue la primera en llegar, aunque quiero aceptar ambas porque ambas me dieron más comprensión sobre el problema. Espero que entiendas….
Tsuyoshi Ito
44
Agradable. Esta es una respuesta genial.
Daniel Apon
@Tyson Williams: en caso de que no se haya dado cuenta, tenga mucho cuidado de no introducir un error cuando edite una publicación de otros usuarios. Fue una suerte que Joe lo notara y lo corrigiera.
Tsuyoshi Ito
18

Respondiendo a la pregunta de Scott Aaronson, pero un poco demasiado largo para un comentario, aquí hay una construcción de un lenguaje tal que P = N P implica L P , pero P N P implica L P H .LP=NPLPPNPLPH

Sean y t ( n ) como en la construcción de Scott. Hacemos que L no se reduzca a Σ k S A T para cada k , pero solo hacemos esto si t ( n ) (es decir, si P N P ). La construcción se desarrolla por etapas. En la etapa s = ( i , j )M1,M2,M3,t(n)LΣkSATkt(n)PNPs=(i,j)(usando algunos biyección fácilmente computable y fácilmente invertible ), nos aseguramos de que M i no es un mucho-uno reducción de L a Σ j S A T . Supongamos que n s es el menor entero tal que t ( n s ) > t ( n s - 1 ) (caso base: n 0 = 1 ). Si existe tal número entero n s , establezcaΣΣ×ΣMiLΣjSATnst(ns)>t(ns1)n0=1ns . Si no existe tal número entero n es , dejamos que L estar vacío para siempre.L(1ns)=1ΣkSAT(Mi(1ns))nsL

Si , entonces t ( n ) como n , así que siempre hay un tal n s , por lo tanto L no se encuentra en P H . Si P = N P , entonces mi L es sólo un número finito diferente de de Scott L , y por lo tanto está en P .PNPt(n)nnsLPHP=NPLLP

Joshua Grochow
fuente
Gracias por su respuesta, pero no estoy seguro si entiendo la construcción. Me parece que para calcular , podría ser necesario buscar indefinidamente y, por lo tanto, me parece que no tenemos un algoritmo explícito para decidir el lenguaje L. Si no necesitamos un algoritmo explícito, la respuesta de Ravi Boppana muestra que existe un lenguaje L tal que P = NP⇒L∈P y P ≠ NP⇒L∉R (es decir, L es indecidible). ns
Tsuyoshi Ito
1
@Tsuyoshi Ito: Yo no creo que haya que calcular dada s con el fin de decidir L; todo lo que tiene que hacer es, en la entrada 1 n , decidir si n es de la forma n es para algunos s , y averiguar qué es que es (si lo hay). Aquí se explica cómo: en la entrada 1 n , calcule t ( n ) y calcule t ( m ) para todos los m < n . Si hay un m < n tal que t ( nnss1nnnsss1nt(n)t(m)m<nm<n , entonces n no es n s para ningún s , entonces L ( 1 n ) = 0 . De lo contrario, descubra qué etapa s corresponde a esta n s (lo que se puede hacer ya que calculó todos los valores anteriores de t ) y luego calcule L ( 1 n ) como se describe en la respuesta. t(n)=t(m)nnssL(1n)=0snstL(1n)
Joshua Grochow