Dowody, bariery i P vs NP

Powszechnie wiadomo, że każdy dowód rozwiązujący pytanie P vs NP musi pokonać relatywizację , dowody naturalne i bariery algebrizacyjne . Poniższy schemat dzieli „przestrzeń próbną” na różne regiony. Na przykład $RN$ odpowiada zestawowi dowodów relatywizujących i naturalizujących. $GCT$ (Teoria złożoności geometrycznej) jest oczywiście ściśle poza regionem.

Wymień kilka dowodów wraz z najbardziej znanymi regionami, do których należą. Umieścić je w najlepszy możliwy sposób, czyli, czy dowód jest znany zrelatywizować, Naturalize i algebrize to powinno być umieszczone w $RNA$ nie tylko w $RN$ . Jeśli dowód relatywizuje się, ale nie naturalizuje, należy do $R$ ${\setminus}$ $N$ i tak dalej.

Myślę, że musisz przerysować swój diagram Venna ... każde ograniczenie klas złożoności, które relatywizuje, również ulegnie algebrize, przynajmniej w sensie Aaronsona i Wigdersona. Oznacza to, że dostęp do „przedłużenia niskiego stopnia” wyroczni jest tylko potężniejszy niż dostęp do wyroczni. Podobnie, wszelkie wyrocznie pokazujące, że separacja wymaga technik „niealgebryzujących” implikuje, że wymagane są również techniki „nierelatywizujące”.

W przeciwieństwie do niektórych wcześniejszych twierdzeń w tym wątku, algebrizacja w sensie Aaronsona i Wigdersona nie jest znana z relatywizacji. Na przykład,

jest stwierdzeniem, które relatywizuje. (W rzeczywistości ma relatywizujący dowód, cokolwiek by to mogło znaczyć dla czytelnika.) Ale algebrize nie jest znane, o czym wspominali sami Aaronson i Wigderson w rozdziale 10.1 swojej pracy [1]. (W rezultacie, chociaż AW mówi nam, że na powyższym diagramie musi leżeć poza , można sobie wyobrazić, że leży w środku!)$\mathsf{NEXP} \not\subset \mathsf{P/poly}$$\mathrm {A}$$\exists \mathcal{C}: \mathcal{C} \subset \mathsf{NEXP} \wedge \mathcal{C} \not \subset \mathsf{P/poly}$

Jednak ostatnie dzieło Erica Bacha i mnie [2] zawiera sformułowanie algebriacji, które obejmuje relatywizację. Zasadniczo, jeśli weźmiemy AW pojęcie algebraicznej wyroczni --- oznaczonej jako dla jakiegoś języka --- i odpowiednio ją zmodyfikujemy, wówczas możemy wyeliminować patologie, takie jak powyżej.$\tilde O$$O$$(\dagger)$

Rezultatem jest to, że algebrizacja, jeśli jest odpowiednio zdefiniowana, to relatywizacja względem algebraicznej wyroczni --- relatywizacja algebraiczna, w której każda wyrocznia otrzymuje „poruszenie” --- co oznacza jest pustym zestawem na powyższym diagramie, stąd też .R $\mathrm{R} \setminus \mathrm{A}$$\mathrm{RN}$

[1] http://www.scottaaronson.com/papers/alg.pdf
[2] http://eccc.hpi-web.de/report/2016/040/

PS: Wcześniej Impagliazzo, Kabanets i Kolokolova zaproponowali inną formułę algebriacji, która również umieszcza wewnątrz , ale nie jest znana jako tak potężna jak koncepcja AW. Zobacz mój artykuł z Erikiem dla porównania.$\mathrm{R}$$\mathrm{A}$

Te twierdzenia czas i przestrzeń hierarchii zrelatywizować. Są jednolite, więc nie wydają się naturalizować.

Myślę, że wyniki pośredniej diagonalizacji, takie jak dolne granice TimeSpace Lance'a Fortnowa i in. a także wynik Ryana Williamsa nie jest relatywizowany, ponieważ nie są czarnymi skrzynkami (ale nie jestem tego pewien). Dowody nie wydają się naturalizować, ponieważ używają twierdzeń hierarchicznych.

Dowody trwałego braku jednolitej$TC^0$ używają twierdzeń hierarchicznych i nie wydają się działać w przypadku niejednorodnych przypadków i nie wydają się naturalizować. Z drugiej strony nie wiem, czy się relatywizują, mogą mieć odpowiednie pojęcie relatywizacji.

Dowody interaktywne nie są relatywizowane. Nie sądzę, by się naturalizowali, ponieważ są mundurowi.