Status der unteren Schaltkreisgrenzen für polylogbegrenzte Tiefenschaltungen

17

Die Schaltungskomplexität mit begrenzter Tiefe ist eines der Hauptforschungsgebiete der Schaltungskomplexitätstheorie. Dieses Thema hat Ursprünge in Ergebnissen wie "Die Paritätsfunktion befindet sich nicht in " und "Die Mod- Funktion wird nicht von berechnet ", wobei die Klasse ist von Sprachen, die durch ungleichmäßige, konstante Tiefe, Polynomgröße, unbegrenzte Fan-In-AND-, OR-, NOT- und Modulo- Gatter entscheidbar sind, wobei . Konkrete Untergrenzen für polylogarithmische Tiefenschaltungen zu erhalten, scheint jedoch mit klassischen Methoden wie der Einschränkung von Eingaben und der Approximation von Polynomen auf endlichen Feldern unerreichbar zu sein.AC0pAC0[q]AC0[q]qgcd(p,q)=1

Ich kenne ein STOC'96-Papier, das zur Theorie der geometrischen Komplexität führt und das zeigt, dass effizientes paralleles Rechnen mit Operationen ohne bitweise Operationen das Min-Cost-Flow-Problem nicht berechnen kann.

Dies bedeutet, dass wir in bestimmten eingeschränkten Einstellungen Untergrenzen für ein vollständiges Problem nachweisen können.PNCP

Erstens, gibt es andere Methoden oder Techniken, die plausible Ansätze für den Nachweis der unteren Grenzen eines polylogarithmischen Tiefenkreislaufs sein könnten?

Zweitens, wie nützlich ist die folgende Aussage für die Theorie-Community?

Die Größe eines - Schaltung eine Boolesche Funktion Berechnung mindestens , wobei einige mathematische Größe ist abhängig von der Härte des Zielfunktion . Der Wert von kann zum Beispiel eine kombinatorische Größe wie Diskrepanz, eine lineare algebraische Größe wie der Rang einer bestimmten Art von Matrix über einem Feld oder eine völlig neue Größe sein, die bisher in der Komplexitätstheorie nicht verwendet wurde.f : { 0 , 1 } n{ 0 , 1 } l l f lNCf:{0,1}n{0,1}llfl

Shen
quelle
6
Ein Wort der Vorsicht ist angebracht: Selbst die logarithmische Tiefe ist weit davon entfernt, verstanden zu werden. Wir haben noch keine superlineare (!) Untergrenze für NC ^ 1-Kreise. Hier ist die Matrixsteifigkeit eine gewünschte "kombinatorische Größe", aber es fehlen ausreichend starke Untergrenzen für diese Größe. Noch bedrückender ist, dass für NC ^ 1-Schaltungen, die eine lineare Transformation f (x) = Ax über GF (2) berechnen, keine superlineare Untergrenze bekannt ist, selbst wenn nur Fanin-2-XORs als Gatter zulässig sind. (Fast alle Matrizen A benötigen dann etwa n ^ 2 / \ log n Tore in beliebiger Tiefe.)
Stasys
@Stasys, ich denke dein Kommentar kann eine Antwort sein.
Kaveh

Antworten:

16

Bei Techniken zum Nachweisen der unteren Grenzen der Poly-Log-Schaltungstiefe funktionieren alle aktuellen Ansätze unter eingeschränkten Einstellungen. Wie in der von Ihnen erwähnten Arbeit zu GCT gilt die Untergrenze für ein eingeschränktes PRAM-Modell ohne Bitoperationen.

Unter einer anderen Einschränkung, der monotonen Einschränkung für monotone Boolesche Funktionen, gibt es in meiner gemeinsamen Arbeit mit Aaron Potechin ( ECCC und STOC ) einen Fourier-analytischen (oder enumerativ-kombinatorischen) Ansatz zum Nachweis monotoner Schaltkreistiefen- Untergrenzen . Dies ist eine Verbesserung gegenüber einem früheren Ergebnis von Ran Raz und Pierre McKenzie, die das Kommunikationsspiel-Framework von Mauricio Karchmer und Avi Wigderson in Bezug auf die Schaltungstiefe erweitern.

Eine weitere Forschungslinie zur Erweiterung des Karchmer-Wigderson-Spiels wurde von Scott Aaronson und Avi Wigderson als Kommunikationsspiel vorgeschlagen , dessen Erweiterung auf ein Konkurrenten-Prüfer-Protokoll als Ansatz zur Trennung von NC und P von Gillat Kol und Ran Raz ( ECCC und ITCS ).

Abgesehen von der Untersuchung der syntaktischen Einschränkung der Monotonie gibt es einen Ansatz zur Untersuchung einer semantischen Einschränkung im Zusammenhang mit Kieselspielen (sogenannte sparsame Verzweigungsprogramme) von Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman und Rahul Santhanam. Es gibt eine starke Untergrenze unter der Sparsamkeitsbeschränkung von Dustin Wehr, die der bekanntesten Obergrenze für P-vollständige Probleme entspricht. Diese Ergebnisse betreffen die Komplexität des deterministischen Raums, der durch bekannte Simulationsergebnisse (z. B. seit ) die Grenzen der parallelen Zeit oder der Schaltkreistiefe unterschreitet .AlternatingTime[t]DeterministicSpace[t]

Über die Frage bezüglich der Größe und Tiefe von Schaltkreisen kann der folgende Ansatz in Beziehung gesetzt werden. Richard Lipton und Ryan Williams zeigen, dass bei einer ausreichend starken Untergrenze der Tiefe (dh ) eine schwach große Untergrenze (dh ) möglich ist trennen Sie NC von P. Dieses Ergebnis ergibt sich aus einem Größen-Tiefen-Kompromiss-Argument, das auf block-respektierenden Simulationen basiert. Ein früheres Ergebnis zur Handelstiefe in Bezug auf die Größe ist Allender und Koucký zuzuschreiben, die auf der Idee der Selbstreduzierbarkeit beruhten, aber kleinere Komplexitätsklassen wie NC und NL untersuchten. n 1 + Ω ( 1 ) 1n1O(1)n1+Ω(1)1

Es ist zu beachten, dass unter den oben erwähnten Ansätzen einige sowohl die Größe als auch die Tiefe von Schaltkreisen berücksichtigen, während andere Ansätze nur die Schaltkreistiefe berücksichtigen. Insbesondere der semi-algebro-geometrische Ansatz von Mulmuley , der von Kol-Raz untersuchte Ansatz des Konkurrenten- Prüfer -Protokolls und der Kompromissansatz zwischen Größe und Tiefe von Allender-Koucký und Lipton-Williams betreffen sowohl die Größe als auch die Tiefe von Schaltungen. Die Ergebnisse in Chan-Potechin , Raz-McKenzie , Cook-McKenzie-Wehr-Braverman-Santhanam und Wehr ergeben bei eingeschränkten Einstellungen unabhängig von der Größe untere Grenzwerte für die Schaltungstiefe. Auch das erwähnte Kommunikationsspiel vonAaronson-Wigderson betrifft nur die Schaltungstiefe.

Es stimmt nach wie vor mit unserer Kenntnis überein, dass ein P-vollständiges Problem nicht durch Schaltkreise mit geringer Tiefe (dh ) berechnet werden kann , unabhängig von der Größe. Wenn die Größe für Schaltkreise mit geringer Tiefe (mit begrenztem Fan-In) keine Rolle spielt, ist es möglicherweise sinnvoll, sich mehr auf die Schaltkreistiefe als auf die Größe von Schaltkreisen mit geringer Tiefe zu konzentrieren.logO(1)n

Siuman
quelle
Vielen Dank! Soweit Sie wissen, wird eine Aussage in Q2 nicht von allen gefunden, oder? Das heißt, im Gegensatz zu Kommunikationskomplexitätsmethoden mit unteren Grenzen haben wir keine mathematische Größe, die die unteren Grenzen der NC-Schaltung angibt.
Shen
@shen, ich habe am Ende noch zwei Absätze hinzugefügt. Hoffe, dass es hilfreich ist.
Siuman
2
Die im Lipton-Williams-Artikel verwendete Idee, dass Untergrenzen mit geringer Größe verstärkt werden können, ist eigentlich Allender und Koucký zu verdanken ( eccc.hpi-web.de/report/2008/038 ).
Emil Jeřábek unterstützt Monica am
@ EmilJeřábek Danke! Ich habe das Papier hinzugefügt. Hoffe, dass die Antwort jetzt besser aussieht.
Siuman
14

Dem Vorschlag von Kaveh folgend, stelle ich meinen Kommentar als (erweiterte) Antwort zur Verfügung.

In Bezug aufQ1 ist ein Wort der Vorsicht angebracht: Selbst logarithmische Tiefe, wenn sie nicht verstanden wird, nicht über polylogarithmische. In der nicht-monotonen Welt ist das eigentliche Problem also viel weniger ehrgeizig:

Beating Log-Depth Problem: Beweisen Sie eine superlineare (!) Untergrenze für Kreise. NC1

Das Problem bleibt (seit nunmehr über 30 Jahren) auch für lineare Schaltungen offen. Dies sind Fan-in- Kreise über die Basis und sie berechnen lineare Transformationen über . Einfaches Zählen zeigt, dass fast alle Matrizen Tore in beliebiger Tiefe benötigen . NC12{,1}f(x)=AxGF(2)AΩ(n2/logn)

ZuQ2 : Ja, wir haben einige algebraische / kombinatorische Maßnahmen, deren untere Schranken die log-tiefen Schaltkreise übertreffen würden. Leider können wir diese Maßnahmen bisher nicht ausreichend einschränken. Nehmen wir zum linearen -Schaltungen, eine solche Maßnahme ist die Steifigkeit der Matrix . Dies ist die kleinste Anzahl von Einträgen von , die geändert werden muss, um den Rang auf zu reduzieren . Es ist leicht zu zeigen, dass für jede boolesche MatrixNC1 RA(r)AArRA(r)(nr)2n×nA, und Valiant (1977) hat gezeigt, dass diese Grenze für fast alle Matrizen eng ist. Um log-tiefe Schaltungen zu schlagen, reicht es aus, eine Folge von booleschen Matrizen so dassn×nA

RA(ϵn)n1+δ für Konstanten . ϵ,δ>0

Das Beste, was wir bisher wissen, sind Matrizen mit . Für Sylvester Matrizen (dh Skalarprodukt Matrices), die der unteren gebunden ist leicht zu zeigen . ARA(r)(n2/r)log(n/r)Ω(n2/r)

Wir haben kombinatorische Maße auch für allgemeine (nichtlineare) Schaltkreise. Für einen zweigliedrigen Graphen sei die kleinste Zahl so dass als Schnittpunkt von bipartite Graphen, wobei jeder eine Vereinigung von höchstens vollständigen bipartiten Graphen. Um die allgemeinen logarithmischen Schaltkreise zu übertreffen, wäre es ausreichend, eine Folge von Graphen mit zu findenNC1n×nGt(G)tGtt

t(Gn)nϵ für eine Konstanteϵ>0

(siehe zB hier, wie das passiert). Wieder haben fast alle Graphen . Das Beste bleibt jedoch eine untere Schranke für Sylvester-Matrizen aufgrund von Lokam . t(G)n1/2t(G)log3n

Lassen Sie mich abschließend erwähnen, dass wir sogar ein "einfaches" kombinatorisches Maß (Quantität) für eine schwache (lineare) Untergrenze haben, an der sich sogar exponentielle (!) Untergrenzen für nicht-monotone Schaltungen ergeben würden. Für einen zweigliedrigen Graphen sei die kleinste Anzahl von Fanin- Vereinigungs- ( ) und Kreuzungsoperationen ( ), die erforderlich sind, um zu erzeugen, wenn von Sternen ausgegangen wird ; Ein Stern ist eine Reihe von Kanten, die einen Scheitelpunkt mit allen Scheitelpunkten auf der anderen Seite verbinden. Fast alle Graphen haben . Andererseits eine Untergrenze vonn×nGc(G)2Gc(G)=Ω(n2/logn)

c(Gn)(4+ϵ)n für eine Konstanteϵ>0

würde eine untere Schranke für die nicht-monotone Schaltungskomplexität einer expliziten Booleschen Funktion von Variablen . Wenn ist Graph mit , dann auch eine untere Schranke genug ist (wieder, siehe zB hier auf , wie dies geschieht). Die unteren Grenzen können für relativ einfache Graphen gezeigt werden. Das Problem besteht jedoch darin, dies zu tun, indem " " durch " " ersetzt wird. Mehr kombinatorische Maßnahmen begrenzen die Schaltungskomplexität (einschließlich desΩ(2N/2)fGNGn×mm=o(n)c(Gn)(2+ϵ)nc(G)(2ϵ)nϵ+ϵACC-Schaltungen) finden Sie im Buch .

PS: Sind wir also um einen konstanten Faktor von von der Darstellung von ? Natürlich nicht. Ich erwähnte das letztere Maß nur, um zu zeigen, dass man die "Verstärkung" (oder "Vergrößerung") der unteren Schranken mit einem gesunden Teil der Skepsis behandeln sollte: obwohl die Schranken, die wir brauchen, "unschuldig" aussehen, sind sie viel kleiner ( linear), als es fast alle Graphen erfordern (quadratisch), kann die inhärente Schwierigkeit, eine (schwache) Untergrenze zu beweisen, sogar noch größer sein. Nachdem wir ein kombinatorisches Maß gefunden haben, können wir natürlich etwas darüber sagen , welche Eigenschaften von Funktionen sie rechenintensiv machen. Dies kann zum Nachweis einer indirekten nützlich sein2+ϵPNPc(G)Untergrenze: Einige Komplexitätsklassen enthalten eine Funktion, die große Schaltkreise oder Formeln erfordert. Das ultimative Ziel ist es jedoch, eine explizite Hard-Funktion zu entwickeln, deren Definition keinen "algorithmischen Geruch" aufweist und die keine versteckten Komplexitätsaspekte aufweist.

Stasys
quelle
2
Ich finde das sehr interessant: 1. Die superlineare untere Schranke für lineare Funktionen über scheint eine sehr konkrete untere Schrankenfrage zu sein. 2. Untergrenzen für mathematische Konzepte, die nicht direkt mit der Berechnung zusammenhängen, beziehen sich auf die Schaltkreisuntergrenze. GF(2)
Kaveh
Matrixsteifigkeit ist ein scheinbar einigendes Konzept, jedoch scheint ihre Struktur in starkem Kontrast zu fast allen Untergrenzen zu stehen, die als ausgedrückt werden , wohingegen sie in Begriffen statt (oder etwa ausgedrückt wird wobei die Eingabegröße ist, da dies für quadratische Matrizen gilt. Hat jemand andere Möglichkeiten gesehen, um die Matrixsteifigkeit auszudrücken, z. B. in Form von ? Ω ( f ( n , r ) ) Ω ( f ( Ω(f(n))Ω(f(n,r))nΩ(f(n))Ω(f(n,r))nΩ(f(n))
vzn
@vzn: Die stärkste untere Schranke von independent oder ist , weil . Ich fürchte, Sie verstehen falsch, was Starrheit eigentlich bedeutet. r 0 R A ( n ) = 0RA(r) r0RA(n)=0
Stasys