Consensus sur P = NP dans un monde où RP = NP

12

est largement supposé être faux.RP=NP

Mais imaginez un instant que c'est vrai. Dans ce cas, quelle serait la probabilité que ?P=NP

En d'autres termes: dans un monde où , qu'est-ce qui pourrait encore être considéré comme un obstacle pour nous de croire P = N P ?RP=NPP=NP

cc.complexity-theory complexity-classes conditional-results Giorgio Camerani
la source
3
En d'autres termes, vous demandez un oracle par rapport à quel RP = NP mais P NP. ≠
Yuval Filmus
Oui. Je voudrais savoir si, dans un monde où , les conditions supplémentaires qui doivent être vrai pour P ≠ N P sont plus strictes et peu probable que les conditions supplémentaires qui doivent être vrai pour P = N P . RP=NPP≠NPP=NP
Giorgio Camerani
7
@Yuval Filmus: Je ne sais pas si la question concerne la barrière de relativisation, mais si c'est le cas, alors il y a un oracle par rapport auquel RP = EXP (ce qui implique P ≠ RP = NP). Je ne peux pas trouver la référence pour ce fait maintenant, mais elle est indiquée dans la remarque après le théorème 6 dans Heller 1986 avec des références à deux articles de Kurtz et de Heller, tous deux dans les actes de la «Conférence sur la théorie de la complexité computationnelle» en mars 1983.
Tsuyoshi Ito

Réponses:

14

Honnêtement, je ne pense pas que Stack Exchange soit un endroit approprié pour demander une prévision future. Malgré cela, je posterai une réponse car c'est amusant de jouer avec l'idée de la bonne aventure.

Pour autant que je sache, la possibilité de P ≠ RP = NP n'a pas été exclue. En outre, il existe une langue A tels que RP A = EXP A [Hel83, Kur83], ce qui implique immédiatement que P A ≠ RP A = NP A . (Je n'ai pas vérifié [Hel83] ou [Kur83], et j'ai pris le résultat et les références de la remarque après le théorème 6 dans [Hel86].) En d'autres termes, même prouver l'implication RP = NP ⇒ P = NP nécessite un technique non relativisante, et il est donc compréhensible que cette implication n'ait pas été prouvée.

(Lance Fortnow a discuté d'un résultat similaire dans le blog Computational Complexity: Oracle Results are Good For You .)

Passons maintenant à la partie diseuse de bonne aventure.

Dans quelle mesure ce résultat oracle révèle-t-il la probabilité de P = NP dans le monde où RP = NP a déjà été prouvé? Pas tant. À tout le moins, il ne faut pas considérer comme preuve que dans le monde où RP = NP a été prouvé, il est encore difficile de prouver P = NP. Dans un tel monde, certaines techniques puissantes et non relativisantes nouvelles sont connues de l'homme, et il ne serait donc pas raisonnable d'interpréter «nécessite une technique non relativisante» comme preuve de difficulté.

De manière plus générale, si RP = NP a été prouvé malgré toutes les croyances (et aussi les barrières de la technique de preuve) à son encontre, alors notre compréhension intuitive actuelle du calcul efficace est probablement très erronée. De toute évidence, nous ne pouvons pas appliquer notre intuition actuelle à la raison du monde où notre intuition actuelle échoue de façon spectaculaire. Je ne pense pas que nous puissions faire une supposition éclairée sur un tel monde, sauf pour ce qui a été rigoureusement prouvé.

Les références

[Hel83] Hans Heller. Sur les hiérarchies polynomiales relativisées s'étendant à deux niveaux. Dans Actes de conférence sur la théorie de la complexité informatique , pp. 109-114, UC Santa Barbara, mars 1983.

[Hel86] Hans Heller. Sur les classes de complexité exponentielle et probabiliste relativisées. Information and Control , 71 (3): 231–243, déc. 1986. DOI: 10.1016 / S0019-9958 (86) 80012-2 .

[Kur83] S. Kurtz (Stuart A. Kurtz?). La structure fine de NP: Relativisations. Dans Actes de conférence sur la théorie de la complexité computationnelle , pp. 42–50, UC Santa Barbara, mars 1983.

Tsuyoshi Ito
la source
«Évidemment, nous ne pouvons pas appliquer notre intuition actuelle à la raison du monde où notre intuition actuelle échoue de manière spectaculaire» ... c'est une grande déclaration.
T ....