Konsensus w sprawie P = NP w świecie, w którym RP = NP

12

jest powszechnie przypuszczane, że jest fałszywe.RP.=N.P.

Ale wyobraź sobie przez chwilę, że to prawda. W takim przypadku, jakie jest prawdopodobieństwo, że ?P.=N.P.

Innymi słowy: w świecie, w którym , co może być nadal postrzegane jako przeszkoda dla nas, aby wierzyć ?RP.=N.P.P.=N.P.

cc.complexity-theory complexity-classes conditional-results Giorgio Camerani
źródło
3
Innymi słowy, prosisz o wyrocznię, w stosunku do której RP = NP, ale P NP. ≠
Yuval Filmus,
Tak. Chciałbym wiedzieć, czy w świecie, w którym , dodatkowe warunki, które muszą być prawdziwe dla P ≠ N P są bardziej rygorystyczne i mało prawdopodobne, niż dodatkowe warunki, które muszą być prawdziwe dla P = N P . RP.=N.P.P.≠N.P.P.=N.P.
Giorgio Camerani,
7
@Yuval Filmus: Nie wiem, czy pytanie dotyczy bariery relatywizacyjnej, ale jeśli tak, to istnieje wyrocznia, w stosunku do której RP = EXP (co oznacza P ≠ RP = NP). Nie mogę teraz znaleźć odniesienia do tego faktu, ale zostało to określone w uwadze po Twierdzeniu 6 w Heller 1986 z odniesieniami do dwóch artykułów Kurtza i Hellera, zarówno w postępowaniu „Konferencji na temat teorii złożoności obliczeniowej” w marcu 1983 r.
Tsuyoshi Ito,

Odpowiedzi:

14

Szczerze mówiąc, nie sądzę, że Stack Exchange to odpowiednie miejsce, aby poprosić o prognozy na przyszłość. Mimo to opublikuję odpowiedź, ponieważ fajnie jest grać z wróżeniem.

O ile mi wiadomo, nie wykluczono możliwości P ≠ RP = NP. Ponadto, nie jest językiem tak, że RP = Exp [Hel83, Kur83], co natychmiast powoduje, że P ≠ RP = NP . (Nie sprawdziłem [Hel83] ani [Kur83] i wziąłem wynik i odniesienia z uwagi po Twierdzeniu 6 w [Hel86].) Innymi słowy, nawet udowodnienie implikacji RP = NP ⇒ P = NP wymaga technika nierelatywizująca, a zatem zrozumiałe jest, że ta implikacja nie została udowodniona.

(Lance Fortnow omawiał podobny wynik na blogu o złożoności obliczeniowej: wyniki Oracle są dobre dla Ciebie ).

Przejdźmy teraz do wróżenia.

Jak bardzo ten wynik wyroczni mówi o prawdopodobieństwie P = NP na świecie, gdzie RP = NP zostało już udowodnione? Niewiele. Przynajmniej nie należy tego traktować jako dowodu, że w świecie, w którym udowodniono RP = NP, nadal trudno będzie udowodnić P = NP. W takim świecie pewne nowe, potężne techniki nierelatywizujące są znane człowiekowi, dlatego też nie byłoby rozsądne interpretowanie „wymaga techniki nierelatywizującej” jako dowodu trudności.

Mówiąc szerzej, jeśli RP = NP zostało udowodnione pomimo wszystkich przekonań (a także udowodnienia barier technicznych), to nasze obecne intuicyjne rozumienie efektywnego obliczenia może być bardzo błędne. Oczywiście nie możemy zastosować naszej obecnej intuicji do rozumowania o świecie, w którym nasza obecna intuicja spektakularnie zawodzi. Nie sądzę, abyśmy mogli w sposób wykształcony zgadywać o takim świecie, z wyjątkiem tego, co zostało rygorystycznie udowodnione.

Bibliografia

[Hel83] Hans Heller. W relatywizowanych hierarchiach wielomianowych rozciągających się na dwa poziomy. W Proceedings of Conference on Computational Complex Theory , s. 109–114, UC Santa Barbara, marzec 1983 r.

[Hel86] Hans Heller. O relatywizowanych wykładniczych i probabilistycznych klasach złożoności. Information and Control , 71 (3): 231–243, grudzień 1986. DOI: 10.1016 / S0019-9958 (86) 80012-2 .

[Kur83] S. Kurtz (Stuart A. Kurtz?). Dobra struktura NP: Relatywizacje. W Proceedings of Conference on Computational Complex Theory , s. 42–50, UC Santa Barbara, marzec 1983 r.

Tsuyoshi Ito
źródło
„Oczywiście nie możemy zastosować naszej obecnej intuicji do rozumowania o świecie, w którym nasza obecna intuicja spektakularnie zawodzi” ... to duże stwierdzenie.
T ....