Bariery w oddzielaniu innych klas złożoności

Czy naturalne dowody , relatywizacja i algebriacja wpływają również na separację innych klas złożoności, takich jak$L\neq NL\neq NP\neq coNP \neq PH\neq PSPACE$ itp?

Na przykład bariera naturalnego dowodu powinna wpływać na każdy dowód $NP\neq CoNP$ ponieważ się rozdzieli $P\neq NP$. Jednak związek między$NP$ i $CoNP$ wydaje się nie mieć wiele z MFW w porównaniu do relacji między $P$ i $NP$. Podobnie naturalne dowody wpływają na silniejsze oddzielenie$NP\neq CoNP$?

Istnieją (przynajmniej) dwa obszary, w których istniejące bariery mają niewiele do powiedzenia:

Dolne granice ACC Nie jest znana bariera dla udowodnienia, że ​​TC0 nie występuje w (nierównomiernym) ACC - poza możliwością, że separacja może być fałszywa. Nie jest jasne, czy bariera Natural Proofs powinna mieć zastosowanie do ACC. Pytanie sprowadza się do: czy należy oczekiwać, że w ACC będą dostępne funkcje pseudolosowe?

LOGSPACE vs NP Jak wskazał Fortnow , istniejące mechanizmy Oracle dla obliczeń związanych z przestrzenią nie wydają się stanowić prawdziwej bariery dla LOGSPACE vs NP. O ile mi wiadomo, znane modele wyroczni, które powodują zawalenie LOGSPACE i NP, również zawalają ALTERNATUJĄCE LOGSPACE (tj. P) i ALTERNATUJĄCE POLYTIME (tj. PSPACE), stąd te wyrocznie traktują naprzemiennie modele obliczeniowe niekonsekwentnie z rzeczywistością (ponieważ LOGSPACE nie jest równy do PSPACE).

Rezultaty Razborova i Rudicha w ich naturalnych papierach próbnych są dość ogólne. Nie jest ograniczony do$\mathsf{P}$ vs. $\mathsf{NP}$.

Osobiście podoba mi się jasność wyjaśnień w najnowszej książce Stasysa Jukny „ Boolean Function Complexity: Advances and Frontiers ”:

Definicja 18.30. Funkcja$G : \{0,1\}^l \to \{0,1\}^n$ z $l < n$ nazywa się $(s,\epsilon)$-bezpieczny pseudolosowy generator, jeśli dotyczy dowolnego obwodu $C$ wielkościowy $s$ na $n$ zmienne,

$$|Pr[C(y) = 1] − Pr[C(G(x)) = 1]| < \epsilon,$$ gdzie $y$ jest wybierany równomiernie losowo w $\{0,1\}^n$, i $x$ w $\{0,1\}^l$.

Definicja 18.31. Pozwolić$f : {0,1}^n \to {0,1}$być funkcją logiczną. Mówimy tak$f$ jest $(s,\epsilon)$-twarde, jeśli na jakikolwiek obwód $C$ wielkościowy $s$,

$$|Pr[C(x) = f(x)] − \frac{1}{2}| < \epsilon,$$ gdzie $x$ jest wybierany równomiernie losowo w $\{0,1\}^n$.

Generator funkcji pseudolosowych jest funkcją logiczną $f(x,y) : \{0,1\}^{n+n^2} \to \{0,1\}$. Ustawiając$y$- zmienne losowe, uzyskujemy jego losową podfunkcję $f_y(x) = f(x,y)$. Pozwolić$h : \{0,1\}^n \to \{0,1\}$być naprawdę losową funkcją logiczną. Generator$f(x,y)$ jest zabezpieczony przed $\Gamma$- atakuje, jeśli dla każdego obwodu $C$ w $\Gamma$,

$$|Pr[C(f_y) = 1] − Pr[C(h) = 1]| < 2^{−n^2}.$$

ZA $\Gamma$-naturalny dowód przeciwko $\Lambda$ jest własnością $\Phi : B_n \to {0,1}$spełniając następujące trzy warunki:
1. Przydatność przeciwko$\Lambda$ : $\Phi(f) = 1$ implikuje $f \notin \Lambda$.
2. Wielkość:$\Phi(f) = 1$ przez co najmniej $2^{−O(n)}$ ułamek wszystkich $2^{2^n}$ Funkcje $f \in B_n$.
3. Konstruktywność:$\Phi \in \Gamma$, to znaczy, gdy spojrzymy na funkcję boolowską w $N = 2^n$ zmienne, właściwość $\Phi$ sama należy do klasy $\Gamma$.

Twierdzenie 18.35. Jeśli klasa złożoności$\Lambda$ zawiera pseudolosowy generator funkcji, który jest bezpieczny przed atakami Γ, więc nie ma $\Gamma$-naturalny dowód przeciwko $\Lambda$.

Pytanie brzmi: 1. Czy uważamy, że istnieją takie trudne funkcje? 2. Jak bardzo konstruktywne / duże oczekujemy właściwości w obecnie możliwych dowodach separacji?

Z drugiej strony Razbarow wspomniał w różnych miejscach, że osobiście postrzega wynik jako wskazówkę, czego należy unikać, a nie jako istotną przeszkodę w udowadnianiu dolnych granic.

Oprócz artykułów Ryana Williamsa w ciągu ostatnich kilku lat wspomniał o dwóch artykułach:

1. Timothy Chow , „ Almost Natural Proofs ”, 2008, w którym stwierdza się, że jeśli nieco rozluźnimy wielkość, to istnieją możliwe do udowodnienia naturalne właściwości, które mogłyby$\mathsf{NP}$ od $\mathsf{P}$.

2. Eric Allender i Michal Koucký , „ Amplifikacja dolnych granic przez środki samoodmienności ”, 2008, który mówi, że należy je rozdzielić$\mathsf{NC^1}$ od $\mathsf{TC^0}$ musimy jedynie udowodnić nieco ponadliniowe dolne granice wielkości $\mathsf{TC^0}$obwody obliczające problem Boolean Formula Evaluation. Istnienie naturalnych dowodów na takie dolne granice nie wydaje się nieracjonalne.

Relatywizacja i algebraizacja są nieco trudniejsze i zależą od sposobu, w jaki definiujemy ponowną aktywację dla tych klas. Ale z reguły prosta diagonalizacja (diagonalizacja, która używa tego samego kontrprzykładu dla wszystkich maszyn obliczających tę samą funkcję, tj. Kontrprzykład zależy tylko od tego, które maszyny w mniejszym komputerze obliczeniowym i nie zależy od ich kodu i sposobu obliczania ) nie może oddzielić tych klas.

Możliwe jest wydobycie nieprostych funkcji diagonalizacji z pośrednich wyników diagonalizacji, takich jak dolne granice czasoprzestrzeni dla SAT.