Consenso sobre P = NP en un mundo donde RP = NP

12

RP=NP es ampliamente conjeturado como falso.

Pero imagine por un momento que es verdad. En tal caso, ¿qué tan probable sería que ?P=NP

En otras palabras: en un mundo donde RP=NP , ¿qué podría verse como un obstáculo para que creamos P=NP ?

cc.complexity-theory complexity-classes conditional-results Giorgio Camerani
fuente
3
En otras palabras, está pidiendo un oráculo en relación con el cual RP = NP pero P ≠ NP.
Yuval Filmus
Si. Me gustaría saber si, en un mundo donde RP=NP , las condiciones adicionales que deben ser ciertas para P≠NP son más estrictas e improbables que las condiciones adicionales que deben ser verdaderas para P=NP .
Giorgio Camerani
77
@Yuval Filmus: No sé si la pregunta es acerca de la barrera de relativización, pero si es así, existe un oráculo en relación con el cual RP = EXP (lo que implica P ≠ RP = NP). No puedo encontrar la referencia para este hecho ahora, pero se afirma en el comentario después del Teorema 6 en Heller 1986 con referencias a dos documentos de Kurtz y de Heller, ambos en las actas de la "Conferencia sobre la teoría de la complejidad computacional" en marzo de 1983.
Tsuyoshi Ito

Respuestas:

14

Honestamente hablando, no creo que Stack Exchange sea un lugar adecuado para pedir una predicción futura. A pesar de esto, publicaré una respuesta porque es divertido jugar con la idea de la adivinación.

Que yo sepa, no se ha descartado la posibilidad de P ≠ RP = NP. Por otra parte, existe un lenguaje A tal que RP A = EXP A [Hel83, Kur83], lo que implica inmediatamente que P A ≠ RP A = NP A . (No he marcado [Hel83] o [Kur83], y tomé el resultado y las referencias del comentario después del Teorema 6 en [Hel86].) En otras palabras, incluso probar la implicación RP = NP ⇒ P = NP requiere un técnica no relativizante y, por lo tanto, es comprensible que esta implicación no haya sido probada.

(Lance Fortnow ha discutido un resultado similar en el blog de Complejidad computacional: los resultados de Oracle son buenos para usted ).

Ahora pasemos a la parte de la adivinación.

¿Cuánto dice este resultado del oráculo sobre la probabilidad de P = NP en el mundo donde RP = NP ya ha sido probado? No mucho. Por lo menos, no debe tomarse como evidencia de que en el mundo donde RP = NP ha sido probado, aún es probable que sea difícil probar P = NP. En un mundo así, el ser humano conoce algunas nuevas y poderosas técnicas no relativizadoras, por lo que no sería razonable interpretar que "requiere una técnica no relativizante" como evidencia de dificultad.

Hablando de manera más amplia, si se ha demostrado RP = NP a pesar de todas las creencias (y también las barreras de la técnica de prueba) en contra de ella, entonces nuestra comprensión intuitiva actual sobre computación eficiente probablemente sea muy errónea. Obviamente, no podemos aplicar nuestra intuición actual a la razón sobre el mundo donde nuestra intuición actual falla espectacularmente. No creo que podamos hacer una conjetura sobre un mundo así, excepto por lo que se ha demostrado rigurosamente.

Referencias

[Hel83] Hans Heller. En jerarquías polinómicas relativizadas que se extienden a dos niveles. En Proceedings of Conference on Computational Complexity Theory , págs. 109-114, UC Santa Bárbara, marzo de 1983.

[Hel86] Hans Heller. En clases de complejidad relativizadas exponenciales y probabilísticas. Información y control , 71 (3): 231–243, diciembre de 1986. DOI: 10.1016 / S0019-9958 (86) 80012-2 .

[Kur83] S. Kurtz (¿Stuart A. Kurtz?). La estructura fina de NP: relativizaciones. En Proceedings of Conference on Computational Complexity Theory , págs. 42–50, UC Santa Bárbara, marzo de 1983.

Tsuyoshi Ito
fuente
"Obviamente no podemos aplicar nuestra intuición actual a la razón sobre el mundo donde nuestra intuición actual falla espectacularmente" ... esta es una gran declaración.
T ....