Was ist die "kleinste" Komplexitätsklasse, für die eine superlineare Schaltungsgrenze bekannt ist?

Entschuldigung für die Frage, die sicherlich in vielen Standardreferenzen enthalten sein muss. Ich bin neugierig auf genau die Frage im Titel, insbesondere denke ich an Boolesche Schaltkreise, die keine Tiefe haben. Ich habe "kleinste" in Anführungszeichen gesetzt, um die Möglichkeit zu berücksichtigen, dass es mehrere verschiedene Klassen gibt, von denen nicht bekannt ist, dass sie sich gegenseitig einschließen, für die eine superlineare Schranke bekannt ist.

Ich glaube , dass die kleinsten solche Klassen bekannt sind (Cai, 2001), P P (Vinodchandran, 2005) und ( M A ∩ c o M A ) / 1 (Santhanam, 2007). Es ist in der Tat bekannt, dass all diese nicht für jede Konstante k in S I Z E ( n k ) sind .$S_2P$$PP$$(MA \cap coMA)/1$$SIZE(n^k)$$k$

Das stärkste Ergebnis, das mir bekannt ist, ist, dass es für alle k ein Problem in , das Schaltkreise der Größe Ω ( n k ) erfordert .$S_2^P$$\Omega(n^k)$

ist eine in Z P P N P enthaltene Klasse, die selbst in Σ P 2 ∩ Π P 2 enthalten ist . (DerKomplexitäts-Zooverfügt über weitere Informationen zu dieser Klasse.)$S_2^P$$ZPP^{NP}$$\Sigma_2^P \cap \Pi_2^P$

Das Ergebnis folgt aus der stärksten Version des Karp-Lipton-Theorems nach Cai .

Ein schneller Beweis, wie dies aus dem KL-Theorem folgt: Erstens, wenn SAT Schaltkreise mit Superpolynomgröße benötigt, sind wir fertig, da wir in ein Problem gezeigt haben, das Schaltkreise mit Superpolynomgröße benötigt. Wenn SAT polynomgroße Schaltkreise hat, kollabiert PH nach der stärksten Version des Karp-Lipton-Theorems zu S P 2 . Wir wissen, dass PH Probleme wie Probleme enthält (nach Kannans Ergebnis), und daher enthält S P 2 ein solches Problem.$S_2^P$$S_2^P$$S_2^P$

Für allgemeine Schaltkreise wissen wir, dass es in Probleme gibt , die Schaltkreise der Größe Ω ( n k ) erfordern. Dies liegt an Ravi Kannan (1981) und beruht auf seinem Ergebnis, dass P H solche Probleme enthält .$\Sigma^p_2 \cap \Pi^p_2$$\Omega(n^k)$$PH$

Ich denke, die besten unteren Grenzen für liegen immer noch bei 5 n .$NP$$5n$

Siehe Arora und Baraks Buch, Seite 297. Richard J. Lipton hatten einen Beitrag auf seinem Blog über diese Ergebnisse, siehe auch diese ein .

Um das zu verfeinern Antwort, für jeden k ≥ 1 und c entweder das 3-SAT Suchproblem nicht über ~ O ( n k ) Schaltungen oder * Einiges Problem in O 2 P mit der Zeit (und Zeugen Größe) beschränkt auf ˜ O ( n k 2 ) hat keine io- O ( n k ( log n ) c ) -Kreise (io bedeutet unendlich oft).$\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)$

Wenn anstelle des 3-SAT-Suchproblems das Entscheidungsproblem verwendet wird, reicht die Zeit ˜ O ( n k 2 + k ) aus, und wenn das Entscheidungsproblem für Bit i in der lexikographisch minimalen Zuordnung für 3-SAT verwendet wird , ~ O ( n min ( k 2 + k , k 3 ) ) genügt.$\mathrm{O}^2\mathrm{P}$$\tilde{O}(n^{k^2+k})$$i$$\tilde{O}(n^{\min(k^2+k,k^3)})$

Ein Entscheidungsproblem nicht berechenbar mit IO- Schaltungen ist die geringste Anzahl N (abgefragt seine Binärziffern verwendet wird ) , die nicht die Wahrheitstabelle einer Schaltung mit ist n k ⌊ ( log n ) c + 1 ⌋ Tore. Wenn NP in P / poly ist, hat das Problem einen unwiderlegbaren, unwissenden Zeugen, der aus Folgendem besteht: (1) N (2) Eine Schaltung, die N ' < N ist , zeigt, dass N ' eine ausreichend kleine Schaltung hat.$O(n^k (\log n)^c)$$N$$n^k ⌊(\log n)^{c+1}⌋$
$N$
$N' < N$$N'$
$\tilde{O}(n^{k^3})$$O(1)$

$k$$O(n^k)$$\mathrm{O}_2\mathrm{P}$$Σ_2^P$$n^{k+1}$$n^{k+2}$$n$$n$