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

25

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.

Matt Hastings
quelle

Antworten:

25

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 .S2PPP(MAcoMA)/1SIZE(nk)k

Ryan O'Donnell
quelle
1
Vielen Dank für die Antworten. Ich akzeptiere Ryan's, da es die größte Vielfalt an Ergebnissen hat, aber ich danke Robin und Kaveh für die detaillierten Erklärungen.
Matt Hastings
20

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 .S2PΩ(nk)

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.)S2PZPPNPΣ2PΠ2P

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.S2PS2PS2P

Robin Kothari
quelle
3
Eine nette und überlegene Antwort wie immer. :)
Kaveh
13

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 .Σ2pΠ2pΩ(nk)PH

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

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

Kaveh
quelle
1

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).S2Pk1c
O~(nk)
O2PO~(nk2)O(nk(Logn)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.O2PO~(nk2+k)ichO~(nMindest(k2+k,k3))

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(nk(Logn)c)Nnk(Logn)c+1
N
N<NN
O~(nk3)O(1)

kO(nk)O2PΣ2Pnk+1nk+2nn

Dmytro Taranovsky
quelle