P / Poly a jednolite klasy złożoności

Nie wiadomo, czy NEXP jest zawarty w P / poli. Rzeczywiście udowodnienie, że NEXP nie jest w P / poli, miałoby pewne zastosowania w derandomizacji.

1. Jaka jest najmniejsza jednolita klasa C, dla której można udowodnić, że C nie jest zawarte w P / poli?

2. Czy wykazanie, że ko-NEXP nie jest zawarty w P / poli, miałoby inne teoretyczne konsekwencje złożoności, jak w przypadku NEXP vs. P / poli?

Uwaga: Zdaję sobie sprawę, że wiadomo, że nie jest zawarty w dla każdej stałej stałej (pokazano to również dla MA z 1 bitem porady). Ale w tym pytaniu nie interesują mnie wyniki dla ustalonego . Naprawdę interesują mnie klasy, które różnią się od P / Poly, nawet jeśli te klasy są bardzo duże.$SP_2$$Size[n^k]$$k$$k$

$\let\mr\mathrm$W literaturze istnieje kilka wyników stwierdzających, że pewna klasa $C$spełnia dla dowolnego , i zwykle łatwo jest je aby pokazać, że żadna ledwie superpolinomicznie wersja nie znajduje się w .$C\nsubseteq\mr{SIZE}(n^k)$$k$$C$$\mr{P/poly}$

Pozwól mi powiedzieć, że jest związkiem wielobiegunowym, jeśli można go konstruować w czasie, a . Na przykład jest związkiem wielobiegunowym. W rzeczywistości ćwiczenie instruktażowe pokazuje, że jeśli jest dowolną nieograniczoną funkcją obliczeniową monotoniczną, to istnieje wielobiegunowa granica taka, że .$f\colon\mathbb N\to\mathbb N$$f(n)=n^{\omega(1)}$$n^{\log\log\log\log n}$$g(n)$$f$$f(n)\le n^{g(n)}$

Po pierwsze, bezpośrednia diagonalizacja pokazuje, że dla dowolnego . Ten sam argument daje:$\Sigma_4^P\nsubseteq\mr{SIZE}(n^k)$$k$

• Jeśli jest jakimkolwiek związkiem , to .$f$$\Sigma_4\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$

  Szkic : dla dowolnego niech będzie pierwszym leksykograficznie obwodem o rozmiarze który oblicza funkcję boolowską w zmiennych, których nie można obliczyć przez obwód o wielkości . Następnie działa język zdefiniowany przez .$n$$C_n$$2f(n)$$n$$<f(n)$$L$$x\in L\iff C_{|x|}(x)=1$

Dobrze znana poprawa stwierdza, że dla dowolnego . Również,$S_2\mr P\nsubseteq\mr{SIZE}(n^k)$$k$

• Jeśli jest jakimkolwiek związkiem wielobiegunowym, to .$f$$S_2\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$

  Dowód szkic: jeśli nie, to w szczególności stąd . Za pomocą argumentu wypełniającego , quod non .$\mr{NP}\subseteq S_2\mr P\subseteq\mr{P/poly}$$\mr{PH}=S_2\mr P$$\Sigma_4\text-\mr{TIME}(f(n))\subseteq S_2\text-\mr{TIME}(f(n))\subseteq\mr{P/poly}$

Nieświadome klasy mają się jeszcze lepiej. Biorąc pod uwagę zarzut podniesiony przez Apoorva Bhagwata, niech . Następnie dla dowolnego , a ten sam argument daje:$\mr{NLin=NTIME}(n)$$\mr{NLin}\cup O_2\mr P\nsubseteq\mr{SIZE}(n^k)$$k$

• Jeśli jest jakimkolwiek związkiem , to .$f$$\mr{NLin}\cup O_2\text-\mr{TIME}(f(n))\nsubseteq\mr{P/poly}$

  Dowód szkic: Jeżeli , a następnie przez napawanie, , która oznacza . Następnie postępujemy jak poprzednio.$\mr{NLin\subseteq P/poly}$$\mr{NP\subseteq P/poly}$$\mr{PH}=O_2\mr P$

Istnieją również wyniki dotyczące MA. Często wspomniany wynik, że to przesada. Santhanam udowodnił dla dowolnego , a podobny argument daje:$\mr{MA\text-EXP\nsubseteq P/poly}$

$$\mr{promise\text-MA\cap promise\text-coMA\nsubseteq SIZE}(n^k)$$ $k$

• Jeśli jest dowolną granicą wielomianową, to $f$

  $$\mr{promise\text-MA\text-TIME}(f(n))\cap\mr{promise\text-coMA\text-TIME}(f(n))\nsubseteq\mr{P/poly}.$$

  Szkic dowodowy: według Lemma 11 Santhanama (która jest zaostrzoną wersją standardowego faktu, że z prover PSPACE), istnieje język kompletny dla PSPACE i randomizowana wyrocznia wielorazowa TM taka, że na wejściu , zadaje tylko wyrocznie zapytania o długości; jeśli , to przyjmuje z prawdopodobieństwem ; a jeśli , to dla dowolnej wyroczni , przyjmuje z prawdopodobieństwem .$\mr{PSPACE=IP}$$L$$M$$x$$M$$|x|$$x\in L$$M^L(x)$$1$$x\notin L$$A$$M^A(x)$$\le1/2$

  Dla odpowiedniego monotonicznego wielomianu , niech będzie problemem obietnicy określonym przez Niech będzie wielomianową redukcją do jego dopełnienia i niech będzie problemem obiecującym $p$$A=(A_{\mr{YES}},A_{\mr{NO}})$

  $$\begin{align} (x,s)\in A_{\mr{YES}}&\iff\exists\text{circuit }C\,\bigl(p(|C|+|x|)\le f(|s|)\land\Pr[M^C(x)\text{ accepts}]=1\bigr),\\ (x,s)\in A_{\rlap{\mr{NO}}\phantom{YES}}&\iff\forall\text{circuit }C\,\bigl(p(|C|+|x|)\le f(|s|)\to\Pr[M^C(x)\text{ accepts}]\le1/2\bigr). \end{align}$$ $h(x)$$L$$B=(B_{\mr{YES}},B_{\mr{NO}})$ $$\begin{align} (x,s)\in B_{\mr{YES}}&\iff(x,s)\in A_{\mr{YES}}\land(h(x),s)\in A_{\mr{NO}},\\ (x,s)\in B_{\rlap{\mr{NO}}\phantom{YES}}&\iff(x,s)\in A_{\mr{NO}}\land(h(x),s)\in A_{\mr{YES}}. \end{align}$$ Jeśli zostanie wybrane odpowiednio duże, Przyjmijmy więc, że ma obwody wielomianowe, powiedzmy . Niech oznacza rozmiar najmniejszego obwodu obliczającego na wejściach o długości , i wstawmy ; a ściślej, Następnie$p(n)$ $$B\in\mr{promise\text-MA\text-TIME}(f(n))\cap\mr{promise\text-coMA\text-TIME}(f(n)).$$ $B$$B\in\mr{SIZE}(n^k)$$s(n)$$L$$n$$t(n)=f^{-1}(p(s(n)))$ $$t(n)=\min\{m:p(s(n))\le f(m)\}.$$ $x\mapsto(x,1^{t(n)})$ jest redukcją do , a więc , co oznacza $L$$B$$L\in\mr{SIZE}(t(n)^k)$ $$s(n)\le t(n)^k.$$ Ale ponieważ$f$ jest super wielomianem, mamy . Daje to sprzeczność dla odpowiednio dużej.$t(n)=s(n)^{o(1)}$$n$

Jeśli wolimy wynik z nie obiecującą wersją MA, Miltersen, Vinodchandran i Watanabe udowodnili o pół wykładniczej funkcji . Możemy to poprawić na dwa sposoby: po pierwsze, utrzymuje -wykładnicze granice dla dowolnej stałej , a po drugie, zachowuje dla klas nieświadomych. Tu, -exponential funkcja jest grubsza, funkcja , tak że

$$\mr{MA\text-TIME}(f(n))\cap\mr{coMA\text-TIME}(f(n))\nsubseteq\mr{P/poly}$$ $f$$\tfrac1k$$k$$\tfrac1k$$f$$\underbrace{f\circ\dots\circ f}_k=\exp$. Zobacz dokument Miltersen – Vinodchandran – Watanabe i zawarte w nim odniesienia w celu uzyskania dokładnej definicji; obejmuje dobrze wychowaną rodzinę dobrze wychowanych funkcji , , tak że , i . Ponadto, jeśli i , a . Potem będzie:$e_\alpha(x)$$\alpha\in\mathbb R_+$$e_0(x)=x$$e_1(x)=e^x-1$$e_{\alpha+\beta}=e_\alpha\circ e_\beta$$f(n)\le e_\alpha(\mr{poly}(n))$$g(n)\le e_\beta(\mr{poly}(n))$$f(g(n))\le e_{\alpha+\beta}(\mr{poly}(n))$

• $\mr{OMA\text-TIME}(e_\alpha)\cap\mr{coOMA\text-TIME}(e_\alpha)\nsubseteq\mr{P/poly}$ dla dowolnego .$\alpha>0$

  Szkic próbny: Załóżmy inaczej. Napraw liczbę całkowitą taką, że . Pozwól mi skrócić Po wypełnieniu mamy dla dowolnego . Ponadto, używając np. Lemma 11 Santhanama powyżej, mamy implikację Ponieważ w sposób trywialny , powtarzająca się aplikacja z (1) i (2) pokazuje$k$$1/k<\alpha$

  $$\mr{OcOMT}(f)=\mr{OMA\text-TIME}(\mr{poly}(f(\mr{poly}(n)))\cap\mr{coOMA\text-TIME}(\mr{poly}(f(\mr{poly}(n))).$$ $$\tag{1}\mr{OcOMT}(e_{\beta+1/k})\subseteq\mr{SIZE}(e_\beta(\mr{poly}(n)))$$ $\beta\ge0$ $$\tag{2}\mr{PSPACE\subseteq SIZE}(e_\beta(\mr{poly}(n)))\implies\mr{PSPACE\subseteq OcOMT}(e_\beta).$$ $\mr{PSPACE\subseteq OcOMT}(e_1)$$\mr{PSPACE\subseteq SIZE}(e_{(k-1)/k}(\mr{poly}(n)))$ ,$\mr{PSPACE\subseteq OcOMT}(e_{(k-1)/k})$ , , i tak dalej. Po kroku dochodzimy do Używając padding jeszcze raz, otrzymujemy co jest sprzeczne z powyższymi wynikami , ponieważ jest granicą wielobiegunową.$\mr{PSPACE\subseteq SIZE}(e_{(k-2)/k}(\mr{poly}(n)))$$\mr{PSPACE\subseteq OcOMT}(e_{(k-2)/k})$$k$ $$\mr{PSPACE\subseteq P/poly}\qquad\text{and}\qquad\mr{PSPACE=OMA\cap coOMA}.$$ $$\mr{DSPACE}(e_{1/k})\subseteq\mr{OcOMT}(e_{1/k})\subseteq\mr{P/poly},$$ $e_{1/k}$

Ponieważ nikt nie opublikował odpowiedzi, sam odpowiem na pytanie komentarzami zamieszczonymi w pierwotnym pytaniu. Dzięki Robin Kothari, Emil Jerabek, Andrew Morgan i Alex Golovnev.

$MA_{exp}$ wydaje się być najmniejszą jednolitą klasą ze znanymi superpolinomialnymi dolnymi granicami.

$O_2^P$ wydaje się być najmniejszą znaną klasą nieposiadającą obwodów o rozmiarze dla każdego ustalonego .$n^k$$k$

Przez diagonalizacji wynika, że dla każdej super wielomian (i przestrzennie konstruowalne) Funkcja , nie ma układów wielomian rozmiarze. kontra jest nadal otwarty.$s$$DSPACE[s(n)]$$PSPACE$$P/poly$

$P/poly$ jest zamknięty pod dopełnieniem, więc zawiera wtedy i tylko wtedy, gdy zawiera .$NEXP$$coNEXP$

Popraw mnie, jeśli się mylę, ale o ile wiem, tak naprawdę nie znamy dolnej granicy wielkości stałej wielomianu dla $O_2^P$. Wynika to z tego, że zwykły argument Karpa-Liptona nie przechodzi$O_2^P$, ponieważ nie wiemy czy $\textsf{NP}\subseteq O_2^P$ (w rzeczywistości jest to równoważne z pytaniem, czy $\textsf{NP}\subseteq \textsf{P/poly}$). Wiemy to jednak$\textsf{NP}^{O_2^P}$ nie jest zawarty w $\textsf{SIZE}(n^k)$ dla każdego $k$, jak pokazują Chakaravarthy i Roy.