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 ?
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 ).
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 .
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.
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.
¿Se sabe algo sobre esto?
fuente
Respuestas:
fuente