Consecuencias de

12

Sabemos que si entonces todo el PH colapsa. ¿Qué pasa si la jerarquía polinómica se colapsa parcialmente? (¿O cómo entender que el PH podría colapsar por encima de cierto punto y no por debajo?)P=NP

En palabras más cortas, ¿cuáles serían las consecuencias de y P N P ?NP=coNPPNP

Xavier Labouze
fuente
3
En ese caso, el PH aún se colapsa (al 1er nivel en lugar del 0º).
Huck Bennett
La primera oración parece expresar que "estamos en problemas si P = NP no se debe a que la jerarquía colapsa", lo cual no es correcto (dejando de lado el posible tema controvertido de si P = NP es una situación problemática o no).
Kaveh
2
@Huck Creo que OP podría estar tratando de preguntar cuáles son las consecuencias del colapso de PH al primer nivel. ¿Qué problemas geniales podríamos resolver entonces?
Artem Kaznatcheev
@Xavier: ¿Por qué dices "... y estamos en problemas" . P = NP, y el consecuente colapso del PH, sería simplemente fantástico ;-)
Giorgio Camerani
@ArtemKaznatcheev: gracias a su comentario comprensivo
Xavier Labouze

Respuestas:

17

Para mí, una de las consecuencias más básicas y sorprendentes de es la existencia de pruebas cortas para una gran cantidad de problemas en los que es muy difícil ver por qué deberían tener pruebas cortas. (Esto es como dar un paso atrás de "¿Qué otras implicaciones de complejidad tiene este colapso?" A "¿Cuáles son las razones básicas y prácticas de este colapso?")NP=coNP

Por ejemplo, si , entonces, para cada gráfico que no sea hamiltoniano, hay una breve prueba de ese hecho. Del mismo modo para los gráficos que no son de 3 colores. Del mismo modo para pares de gráficos que no son isomórficos. De manera similar para cualquier tautología proposicional .NP=coNP

En un mundo donde , la dificultad para probar tautologías proposicionales no es que algunas tautologías cortas tengan pruebas largas, porque en un mundo así cada tautología tiene una prueba polinomialmente corta, sino que hay algunas otra razón por la que no podemos encontrar esas pruebas de manera eficiente.PNP=coNP

Joshua Grochow
fuente
Me gusta esta respuesta! +1
Tayfun paga
Gracias por su respuesta, la consecuencia subrayada es bastante sorprendente. Me pregunto qué otra razón no puede encontrar esas pruebas de manera eficiente. Alguna idea ?
Xavier Labouze
12

Si también asumimos , entonces la hipótesis también causaría el colapso de las clases aleatorias:NP=RP . Aunque todos estos se conjeturan para colapsar incondicionalmente en P , de todos modos, todavía está abierto si eso realmente sucede. En cualquier caso, N P = c o N P no parece implicar en sí mismo que estas clases aleatorias colapsen.ZPP=RP=CoRP=BPPPNP=coNP

Si no lo hacen, es decir, al menos tenemos , entonces, junto con la hipótesis N P = c o N P , esto tendría otra consecuencia importante:BPPPNP=coNP . Esto se deduce del resultado de Babai, Fortnow, Nisan y Wigderson, que dice que si todas (tally) idiomas unarios en P H caen en P , entonces B P P = P . Por lo tanto, si B P PP , entonces pueden no toda la caída en P , como el N P = c o N P supuesto implica P H = N P . Por lo tanto, debe haber un lenguaje de conteo en N P - PENEPHPBPP=PBPPPPNP=coNPPH=NPNPP. Finalmente, la presencia de un lenguaje tally en es bien conocida para implicar EN E .NPPENE

El razonamiento anterior muestra el efecto interesante que el hipótesis, a pesar de ser un colapso, en realidad amplifica la separación de poder de B P PP , ya que éste solo no se conoce implicar EN E . Esta "anomalía" parece apoyar la conjetura B P P = P .NP=coNPBPPPENEBPP=P

Andras Farago
fuente
1
Tal vez estoy siendo lento aquí, pero ¿cómo implica NP = coNP ZPP = RP = coRP = BPP?
Joshua Grochow
@JoshuaGrochow Estoy atrapado en eso también.
Tayfun paga
Gracias, de hecho me perdí una condición. Corrija la respuesta.
Andras Farago
@AndrasFarago está bien! +1 :)
Tayfun paga
@AndrasFarago Tks por tu respuesta!
Xavier Labouze
7

#P

ValiantsDefinition:_C#C=AC(#P)A(#PA)A

#NP=#CoNP

TodasDefinition:_C#.CfCRpxf(x)=||{y|p(|x|)=|y|R(x,y)}||

#.NP=#.CoNPNP=CoNP

PNPFP#P

Tayfun Pay
fuente
Es la versión de conteo de NP.
Tayfun paga el
¿A qué se refiere el período en "# .NP"?
Timothy Sun
44
Hay dos tipos si se cuentan las jerarquías de conteo. Uno de Valiant en 1979 y usa la notación #P, # NP, # Co-NP ... Donde # NP = Co-NP. Por otro lado, Toda definió una jerarquía diferente. Y la notación para eso usa puntos. Y # .NP! = #. Co-NP a menos que NP = Co-NP
Tayfun Pague el
2

Ker-i Ko demostró que hay un oráculo que hace que el PH colapse al nivel k-ésimo. Ver "Ker-I Ko: jerarquías de tiempo polinomial relativizado que tienen exactamente niveles de K. SIAM J. Comput. 18 (2): 392-408 (1989)".

Bin Fu
fuente
¿Puedes vincularnos al periódico?
Tayfun paga el
@ BinFu Tks - Pensé que el PH colapsa al primer nivel ...
Xavier Labouze
1
Para el caso k = 1, es el caso de este problema. El tiempo polinomial colapsa a NP bajo la condición NP = coNP. La existencia del oráculo para el k-ésimo nivel en el artículo de Ko significa la barrera de cualquier método relativizado para tratar el problema del colapso de la HP.
Bin Fu
1
@ BinFu: sus comentarios no describen ninguna consecuencia de PNP = coNP . La pregunta no era cómo mostrar un colapso al primer nivel, o acerca de los resultados que también describen un colapso al primer nivel, sino lo que se conocería como un corolario de un colapso al primer nivel. No veo cómo su respuesta tiene eso en absoluto.
Niel de Beaudrap
1
Cada fórmula booleana satisfactoria tiene una prueba de tiempo y longitud polinómica, que son las asignaciones de verdad para hacer que la fórmula sea verdadera. La condición NP = coNP hace que cada fórmula booleana insatisfactoria tenga una prueba de tiempo y longitud polinómica. Si P no es igual a NP, y NP = coNP, entonces no existe un algoritmo de tiempo polinomial para encontrar la prueba de longitud polinómica para una fórmula booleana para su satisfacción o insatisfacción. Del mismo modo, tendremos conclusiones similares para todos los problemas en NP.
Bin Fu