Separacje klas złożoności bez twierdzeń hierarchicznych

Twierdzenia o hierarchii są podstawowymi narzędziami. Wiele z nich zebrano we wcześniejszym pytaniu (patrz Jakie hierarchie i / lub twierdzenia dotyczące hierarchii znasz? ). Niektóre separacje klas złożoności wynikają bezpośrednio z twierdzeń hierarchicznych. Przykłady takich dobrze znanych separacji: $L\neq PSPACE$ , , , . $P\neq EXP$ $NP\neq NEXP$ $PSPACE\neq EXPSPACE$

Jednak nie każde rozdzielenie wynika z twierdzenia o hierarchii. Bardzo prostym przykładem jest . Chociaż nie wiemy, czy któryś z nich zawiera drugi, są one nadal różne, ponieważ jest zamknięte w odniesieniu do transformacji wielomianowych, podczas gdy nie. $NP\neq E$ $NP$ $E$

Jakie są głębsze, bezwarunkowe, nierelatywizowane separacje klas złożoności dla klas jednolitych, które nie wynikają bezpośrednio z jakiegoś twierdzenia hierarchicznego?

cc.complexity-theory complexity-classes hierarchy-theorems Andras Farago
źródło

Myślę, że to trochę niezwykłe nazywać

separacją. Również ich nierówność jest z trywialnych powodów i nie mówi nam nic ciekawego. AFAIK wszystkie interesujące separacje klas złożoności dla dużych klas złożoności opierają się w pewnym momencie na twierdzeniach hierarchii (i z kolei diagonalizacji).

N P \neq E

$NP\neq E$

Kaveh

To prawda, że nazywanie

separacją jest rzeczywiście niezwykłe , ponieważ ma to trywialne przyczyny. Przywołałem to tylko, aby pokazać prosty przykład, w którym nie jest potrzebne twierdzenie hierarchiczne.

N P \neq E

$NP\neq E$

Andras Farago

Eee, dowód NP! = E ma zależeć od twierdzenia hierarchii! Działa to tak, że najpierw zakłada się NP = E, a następnie używa właściwości zamknięcia NP, aby wywnioskować, że E = EXP, naruszając w ten sposób twierdzenie o hierarchii czasu.

Scott Aaronson

Dziękuję Scott, masz całkowitą rację.

nie był dobrym przykładem. Umieściłem lepszy wśród odpowiedzi.

N P \neq E

$NP\neq E$

Andras Farago

Tak więc, nawet różnice tego rodzaju opiera się na diagonalizacji:

ale

. W końcu miło i nie tak banalnie.

E \subseteq N P \subseteq A C^{0} \circ N P \subseteq A C^{0} \circ E \subseteq E X P

$E \subseteq NP \subseteq AC^0\circ NP \subseteq AC^0 \circ E \subseteq EXP$

E ⊊ E X P

$E \subsetneq EXP$

Kaveh

Odpowiedzi:

Chciałbym być źle pokazany, ale nie sądzę, że istnieją obecnie jednolite dolne granice, które ostatecznie nie są oparte na jednym z twierdzeń hierarchicznych. Nasze obecne rozumienie tego, jak korzystać z jednolitości, jest naprawdę dość ograniczone w tym sensie.

Z drugiej strony istnieje wiele jednolitych dolnych granic, które nie wynikają bezpośrednio z twierdzeń o hierarchii, ale używają twierdzenia o hierarchii w połączeniu z innymi sprytnymi sztuczkami, technikami i wynikami, na przykład:

[Hopcroft-Paul-Valiant]. Udowadniają, że (część dowodu niezwiązana z przekątną), a następnie wykorzystują fakt, że $\mathsf{CSL} \not\subseteq \mathsf{DTIME}(n)$ $\mathsf{DTIME}(n) \subseteq \mathsf{DSPACE}(n/\log n)$ $\mathsf{CSL} = \mathsf{NSPACE}(n)$ w połączeniu z hierarchią przestrzeni. Ich wynik + hierarchia przestrzeni implikuje również . $\mathsf{DSPACE}(n) \nsubseteq \mathsf{DTIME}(n)$
Kompromisy czasoprzestrzenne dla satysfakcji (patrz np. Wprowadzenie Bussa-Williamsa i odniesienia do niego)
[Paul-Pippinger-Szemeredi-Trotter]. Wykorzystuje nietrywialną symulację dowolnej deterministycznej superliniowej maszyny czasu w szybszej maszynie z czterema przemianami, w połączeniu z deterministyczną hierarchią czasu. $\mathsf{DTIME}(n) \neq \mathsf{NTIME}(n)$
Jednolite dolne granice na stałe [ Allender , Allender-Gore , Koiran-Perifel ]
[Williams] (chociaż technicznie jest to nierównomierny dolna granica, wykorzystuje kilka pomysłowe w połączeniu z niedeterministycznych hierarchii czasu) $\mathsf{NEXP} \not\subseteq \mathsf{ACC}^0$

Joshua Grochow
źródło

Jest oddzielenie przez Smoleńskiego coś, czego szukaliśmy? $\mathsf{AC}^0\subsetneq\mathsf{TC}^0$

Arne
źródło

Dziękuję, że jest ładny wynik, ale szukam rozdziałów

klas, a nie klas obwodu.

u n i f o r m

$uniform$

Andras Farago

@AndresFarago: Jednolity AC ^ 0 jest również poprawnie zawarty w jednolitym TC ^ 0.

Emil Jeřábek wspiera Monikę

@ EmilJeřábek: Czy istnieje dowód na to, że mundur

jest właściwie zawarty w mundurze

, który nie dowodzi już również niejednolitej deklaracji? (Jeśli nie, to wydaje się, że twój przykład podlega ogólnej zasadzie, że niejednolite dolne granice są silniejsze niż jednolite dolne granice i myślę, że OQ próbował uniknąć takich odpowiedzi ...)

{A C}^{0}

$\mathsf{AC}^0$

{T C}^{0}

$\mathsf{TC}^0$

Joshua Grochow

Uważam, że niezgodność dowodów jest drugorzędna w stosunku do faktu, że są to raczej małe klasy, w których mamy jakieś dobre kombinatoryczne / algebraiczne ich rozumienie. Tzn. Rozumiemy je wystarczająco dobrze, aby bezpośrednio skonstruować obiekt, którego nie ma w nich. Gdzie są większe klasy, nie ma takiego zrozumienia i dlatego jedyną znaną metodą jest przekątna całej klasy w celu zbudowania takich obiektów.

Kaveh

Kolejny nietrywialny przykład pochodzi z obszaru o średniej złożoności przypadków. Rainer Schuler dowodzi interesujących właściwości klasy, którą nazywa , patrz [1]. $P_{P-comp}$

$P_{P-comp}$ $\mu$ $\mu$ $P\subseteq P_{P-comp}$ $P_{P-comp}=P$

$L\in P_{P-comp}$ $E$ , to jest,

mi \subseteq {P.}^{{P.}_{P. - do o m p}} (*)

$E\subseteq P^{P_{P-comp}}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; (*)$ To implikuje bezwarunkowy rozdział

P_{P - c o m p} \neq P

$P_{P-comp}\neq P$ . Podczas gdy ten drugi również wykorzystuje ten fakt

E \neq P

$E\neq P$ , która wynika z twierdzenia o hierarchii czasu, nowa część (*) opiera się na różnych narzędziach: poza diagonalizacją stosuje miarę ograniczoną do zasobów i złożoność Kołmogorowa.

Odniesienie:

[1] R. Schuler, „Zamknięcie tabeli prawdy i zamknięcie średniego czasu wielomianowego Turinga mają różne miary w EXP”, CCC 1996, pdf

Andras Farago
źródło