Jerarquía polinómica aleatoria?

12

Me pregunto, ¿qué sucedería si en la definición de (Jerarquía polinómica, ver, por ejemplo, aquí ), el papel de N P fuera reemplazado por R P ?PHNPRP

Parece, podríamos construir una jerarquía, del mismo modo que se construye, simplemente usando R P todas partes en lugar de N P y C O R P en lugar de C O N P . Llamémosla Jerarquía polinómica aleatoria ( R P H ).PHRPNPcoRPcoNPRPH

Mi primera suposición es que , o tal vez R P H = B P P . Se basa en el hecho conocido de que N P = R P implica P H = B P P . Sin embargo, si P R P , entonces R P H podría aún haber una jerarquía adecuada, infinito dentro de B P P .RPHBPPRPH=BPPNP=RPPH=BPPPRPRPHBPP

Por supuesto, el borde de la cuestión es mitigado por el hecho de que se conjetura (incluso P = B P P ), lo que aplanar R P H en P . Sin embargo, P = R P no se conoce en este momento, y hasta ahora se ha resistido a todos los intentos de prueba. Por lo tanto, R P H todavía tiene al menos alguna posibilidad de ser una jerarquía adecuada.P=RPP=BPPRPHPP=RPRPH

Si bien , es cierto, tiene una buena oportunidad de ser "plano", ¿podría el concepto seguir siendo útil para algo no trivial? Aquí hay un ejemplo: si uno puede probar R P H = B P P , entonces produciría que P = R P implica P = B P P , lo cual, creo, sería un resultado interesante.RPHRPH=BPPP=RPP=BPP

¿Se sabe algo sobre esto?

Andras Farago
fuente
2
PRP
2
@usul: cs.stackexchange.com/a/26332/12859

Respuestas:

8

RPHBPPBPP=ZPPpromiseRPBPPRPpromiseRP

Emil Jeřábek
fuente