Jaka jest „najmniejsza” klasa złożoności, dla której znane jest obwody superliniowe?

Przepraszamy za zadawanie pytań, które z pewnością muszą znaleźć się w wielu standardowych źródłach. Ciekawi mnie dokładnie pytanie zawarte w tytule, w szczególności myślę o obwodach boolowskich, bez ograniczeń głębokości. W cudzysłowie wstawiam „najmniejszy”, aby umożliwić istnienie wielu różnych klas, o których nie wiadomo, że zawierają się w sobie, dla których znana jest granica superliniowa.

Uważam, że najmniejszymi znanymi tego rodzaju klasami są $S_2P$ (Cai, 2001), $PP$ (Vinodchandran, 2005) i $(MA \cap coMA)/1$ (Santhanam, 2007). Wszystkie z nich rzeczywiście nie są w $SIZE(n^k)$ dla każdej stałej $k$ .

Najsilniejszy wynik, jaki jestem świadomy, to to, że dla wszystkich k występuje problem w $S_2^P$ który wymaga obwodów o wielkości $\Omega(n^k)$ .

jest klasą zawartą w Z P P N P , która sama jest zawarta w Σ P 2 ∩ Π P 2 . (Zoo złożonościma więcej informacji o tej klasie).$S_2^P$$ZPP^{NP}$$\Sigma_2^P \cap \Pi_2^P$

Wynik wynika z najsilniejszej wersji twierdzenia Karp-Lipton spowodowanej przez Cai .

Szybki dowód na to, jak wynika to z twierdzenia KL: Po pierwsze, jeśli SAT wymaga super-wielomianowych obwodów wielkości, jesteśmy skończeni, ponieważ wykazaliśmy w problem, który wymaga super-wielomianowych obwodów. Jeśli SAT ma wielomianowe obwody wielkości, to według najsilniejszej wersji twierdzenia Karp-Lipton PH upada do S P 2 . Wiemy, że PH zawiera problemy takie problemy (na podstawie wyniku Kannana), a zatem S P 2 zawiera taki problem.$S_2^P$$S_2^P$$S_2^P$

W przypadku obwodów ogólnych wiemy, że w występują problemy wymagające obwodów o wielkości Ω ( n k ) , wynika to z Ravi Kannana (1981) i opiera się na jego wyniku, że P H zawiera takie problemy .$\Sigma^p_2 \cap \Pi^p_2$$\Omega(n^k)$$PH$

Myślę, że najlepsze dolne granice dla wciąż wynoszą około 5 n .$NP$$5n$

Zobacz książkę Arory i Baraka, strona 297. Richard J. Lipton miał post na swoim blogu o tych wynikach, zobacz także ten .

$\mathrm{S}_2\mathrm{P}$$k≥1$$c$
$\tilde{O}(n^k)$
$\mathrm{O}_2\mathrm{P}$$\tilde{O}(n^{k^2})$$O(n^k (\log n)^c)$

Jeśli zamiast problemu wyszukiwania 3-SAT użyliśmy problemu decyzyjnego, wystarczy czas ˜ O ( n k 2 + k ) , a jeśli zastosowaliśmy problem decyzyjny dla bitu i w leksykograficznie minimalnym przypisaniu dla 3-SAT , ˜ O ( n min ( k 2 + k , k 3 ) ) wystarcza.$\mathrm{O}^2\mathrm{P}$$\tilde{O}(n^{k^2+k})$$i$$\tilde{O}(n^{\min(k^2+k,k^3)})$

Jednym z problemów decyzyjnych, których nie można obliczyć w obwodach io- jest najmniejsza liczba N (sprawdzana za pomocą cyfr binarnych), która nie jest tabelą prawdy w obwodzie o n k ⌊ ( log n ) c + 1 ⌋ bramy. Jeśli NP jest w P / poli, problem ma niepodważalne, nieświadome świadectwo składające się z: (1) N (2) obwodu, który dał N ′ < N , pokazuje, że N ′ ma wystarczająco mały obwód.$O(n^k (\log n)^c)$$N$$n^k ⌊(\log n)^{c+1}⌋$
$N$
$N' < N$$N'$
(3) (używany tylko dla granicy ) weryfikator, który pozwala nam uruchomić obwód przeciwnika tylko ( 2 ) razy O ( 1 ) razy (otrzymując 1 bit na bieg).$\tilde{O}(n^{k^3})$$O(1)$

$k$$O(n^k)$$\mathrm{O}_2\mathrm{P}$ n k + 1 n k + 2 n$Σ_2^P$$n^{k+1}$$n^{k+2}$, korzystając z porad, aby wykryć wystarczającą liczbę przykładów takiego , i dla tych , rozwiązując problem wyściełany, każąc Merlinowi wytworzyć taki obwód.$n$$n$