Dowody, bariery i P vs NP

25

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.

alternatywny tekst

— Shiva Kintali
źródło

Ale czy są jakieś znane ważne dowody P vs NP w ogóle?

— gphilip

2

Myślę jednak, że to klasyczne pytanie CW.

— Suresh Venkat

@ gphilip Mówimy ogólnie o dowodach z dolnej granicy w teorii złożoności.

— Shiva Kintali,

@Suresh Umieszczanie dowodów w tych regionach jest wysoce nietrywialne. Osoby zamieszczające odpowiedzi powinny być nagradzane (oczywiście większymi głosami) za ich wiedzę i zrozumienie tych barier. Co myślisz ?

— Shiva Kintali,

Po przeczytaniu poniższej odpowiedzi Suresha, myślę, że dostałem pytanie (popraw mnie, jeśli się mylę): szukasz klasyfikacji formularza „Jeśli dowód, który rozwiązuje P w porównaniu z NP, ma właściwość X, to należy on do regionu Y w obrazek." W odpowiedzi Suresha X oznacza „Interactive”, a Y jest poza R, prawdopodobnie również poza N.

— gphilip

17

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”.

— Ryan Williams
źródło

R \subseteq A

$R \subseteq A$

4

To, co mówi Ryan, dotyczy tylko powstrzymywania. Wynik taki jak P = NP oznacza, że P = PH relatywizuje się, ale nie algebrize.

— Lance Fortnow,

@Lance: Dziękujemy za wyjaśnienie. Dlatego sensowne jest pozostawienie schematu bez zmian.

— Shiva Kintali

3

P^{\tilde{A}} = N P^{\tilde{A}}

$P^{\tilde{A}} = NP^{\tilde{A}}$

P H^{A} \subseteq P^{\tilde{A}}

$PH^{A} \subseteq P^{\tilde{A}}$

13

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,

\begin{matrix} (†) & (\exists C : C \subset N E X P \land C ⊄ P / p o l y) ⟹ N E X P ⊄ P / p o l y \end{matrix}

$\tag{$\dagger$}(\exists \mathcal{C}: \mathcal{C} \subset \mathsf{NEXP} \wedge \mathcal{C} \not \subset \mathsf{P/poly})\implies \mathsf{NEXP} \not\subset \mathsf{P/poly}$

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ż . $\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}$

— Barış Aydınlıoğlu
źródło

Dzięki Baris. Cieszę się, że ktoś w końcu znalazł pojęcie algebriacji, która formalnie robi to, co naszym zdaniem powinno być :)

— Ryan Williams

11

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.

— Kaveh
źródło

7

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

— Suresh Venkat
źródło