Schaltungsuntergrenzen über beliebige Sätze von Toren

40

In den 1980er Jahren hat Razborov gezeigt, dass es explizite monotone Boolesche Funktionen gibt (wie die CLIQUE-Funktion), für deren Berechnung exponentiell viele UND- und ODER-Gatter erforderlich sind. Die Basis {AND, OR} über der Booleschen Domäne {0,1} ist jedoch nur ein Beispiel für eine interessante Gate-Menge, die nicht universell ist. Dies führt zu meiner Frage:

Gibt es einen anderen Satz von Gattern, der sich interessanterweise von den monotonen Gattern unterscheidet, für die exponentielle Untergrenzen der Schaltungsgröße bekannt sind (ohne Tiefe oder andere Einschränkungen für die Schaltung)? Wenn nicht, gibt es eine andere Reihe von Toren, die ein plausibler Kandidat für solche Untergrenzen ist - Grenzen, die nicht unbedingt das Durchbrechen der Natural Proofs-Barriere erfordern würden, wie dies bei Razborovs monotonen Schaltkreisen der Fall war?

Wenn ein solches Gate-Set existiert, wird es mit Sicherheit über einem k-ären Alphabet für k≥3 liegen. Der Grund ist, dass über ein binäres Alphabet die

(1) monotone Gatter ({AND, OR}),

(2) lineare Gatter ({NOT, XOR}) und

(3) Universaltore ({AND, OR, NOT})

schöpfen Sie im Grunde genommen die interessanten Möglichkeiten aus, wie aus dem Klassifikationssatz von Post hervorgeht. (Beachten Sie, dass ich davon ausgehe, dass die Konstanten --- 0 und 1 im Binärfall --- immer kostenlos verfügbar sind.) Bei den linearen Gattern ist jede Boolesche Funktion f: {0,1} n → {0,1} das überhaupt berechenbar ist durch eine Schaltung linearer Größe berechenbar; mit einem universellen Set haben wir es natürlich mit Natural Proofs und den anderen furchterregenden Barrieren zu tun.

Betrachtet man dagegen beispielsweise Gate-Mengen über einem 3- oder 4-Symbol-Alphabet, so eröffnet sich eine breitere Palette von Möglichkeiten - und zumindest meines Wissens sind diese Möglichkeiten noch nie vollständig ausgeschöpft worden vom Standpunkt der Komplexitätstheorie (bitte korrigieren Sie mich, wenn ich falsch liege). Ich weiß, dass die möglichen Gate-Sets unter dem Namen "Klone" in der Universalalgebra ausführlich untersucht werden. Ich wünschte, ich wäre vertrauter mit dieser Literatur, damit ich weiß, was die Ergebnisse aus diesem Bereich für die Komplexität von Schaltkreisen bedeuten.

Auf jeden Fall scheint es nicht ausgeschlossen zu sein, dass es andere dramatische Schaltkreisuntergrenzen gibt, die für die Prüfung reif sind, wenn wir einfach die Klasse der Gate-Sets über endliche Alphabete erweitern, die wir zu berücksichtigen bereit sind. Wenn ich falsch liege, sag mir bitte warum!

Scott Aaronson
quelle
3
Wenn Sie die Funktionen berücksichtigen, ist die Situation für lineare Gatter schwieriger, da das Argument counting zeigt, dass es Funktionen gibt, die erfordern zu berechnende Gatter, obwohl es meines Wissens keine expliziten Beispiele für Funktionen gibt, die Schaltungen mit superlinearer Größe erfordern. f:{0,1}n{0,1}nΩ(n2log(n))
Grigory Yaroslavtsev
2
Nur eine Anmerkung: Wenn Sie monotone boolesche Gatter durch Gatter ersetzen, die nicht abnehmende reelle Funktionen berechnen , erhalten Sie auch exponentielle Untergrenzen für die Schaltkreisgröße. Dies wurde von Pudlak bewiesen: Lower bounds for resolution und cutting plane proofs and monotone computations , J. of Symb. Logic 62 (3), 1997, S. 981–998.
Iddo Tzameret
2
Grigory: Danke; Ich überlegte, ob ich das im OP erwähnen sollte! Sie haben Recht, dass wir keine explizite superlineare Untergrenze für die Anzahl der XOR-Gatter haben, die zur Berechnung einer linearen Funktion f: {0,1} <sup> n </ sup> {0,1} <erforderlich sind sup> n </ sup>. Andererseits ist es nicht schwer, Kandidaten für lineare Transformationen zu finden, für die <i> XOR-Gatter </ i> erforderlich sind (die Fourier-Transformation, die "Sierpinski-Dichtung" -Matrix ...). , und Bram Cohen schlugen eine Beispielfunktion vor, die & Omega (n <sup> 3/2 </ sup>) XOR-Gatter erfordern sollte (ich erinnere mich nicht daran, könnte ihn aber fragen).
Scott Aaronson
Selbst für Alphabet 3 ist das Klongitter unzählig und enthält jedes endliche Gitter als Untergitter. Es gibt also unendlich viele möglicherweise interessante Operationsgrundlagen zu berücksichtigen. Mir sind keine Arbeiten zur Verwendung von nicht-booleschen Klonen für Schaltkreisuntergrenzen bekannt, aber dies scheint es wert zu sein, eingehender untersucht zu werden.
András Salamon
3
Scott, kennen Sie ein passendes Analogon für die Klasse AC ^ 0 gegenüber größeren Aphabeten? Lassen Sie mich auch bemerken, dass man Begriffe der Monotonie für größere Alphabete in Betracht ziehen kann (Elchanan Mossel und ich haben über scharfe Schwellenwerte für jene Front.Math.UCDAVIS.EDU/1011.3566 geschrieben ) Monotonie.
Gil Kalai

Antworten:

25

(Von Kommentaren verschoben, wie von Suresh vorgeschlagen. Beachten Sie, dass hier einige Fehler im Kommentar behoben sind.)

Vielen Dank an Scott für eine tolle Frage.

Scott scheint anzunehmen, dass der Grund für die Schwierigkeit der Untergrenzen in der eingeschränkten Betriebssprache im Booleschen Fall liegen könnte. Shannons Zählargument, das zeigt, dass die meisten Schaltkreise groß sein müssen, beruht auf der Lücke zwischen zählbarer Ausdruckskraft und unzählig vielen Schaltkreisen. Diese Lücke scheint zu verschwinden, wenn das Alphabet mindestens 3 Symbole enthält.

Für Alphabetgröße 2 (der Boolesche Fall) ist das Gitter der Klone zählbar unendlich und wird als Post-Gitter bezeichnet .

Das Gitterbild des Posts aus Wikipedia

Das Gitter von Post macht auch deutlich, warum es für den Booleschen Fall nur wenige interessante Operationsgrundlagen gibt.

Ab Alphabetgröße 3 ist das Klongitter unzählig. Ferner erfüllt das Gitter keine nichttriviale Gitteridentität, so dass es unmöglich erscheint, eine vollständige Beschreibung des Gitters bereitzustellen. Ab Alphabetgröße 4 enthält das Klongitter tatsächlich jedes endliche Gitter als Untergitter. Es gibt also unendlich viele möglicherweise interessante Grundlagen für Operationen, die zu berücksichtigen sind, wenn das Alphabet 3 oder mehr Symbole enthält.

  • Bulatov, Andrei A., Durch Klongitter erfüllte Bedingungen , Algebra Universalis 46 237–241, 2001. doi: 10.1007 / PL00000340

Scott fragte weiter: Bleibt das Gitter der Klone unzählig, wenn wir annehmen, dass Konstanten kostenlos verfügbar sind?

Die Antwort ist, dass dies z. B. der Fall ist

  • Gradimir Vojvodić, Jovanka Pantović und Ratko Tošić, Die Anzahl der Klone mit einer unären Funktion , NSJOM 27 83–87, 1997. ( PDF )
  • J. Pantović, R. Tošić und G. Vojvodić, Die Kardinalität funktional vollständiger Algebren an einem Dreielementensatz , Algebra Universalis 38 136–140, 1997. doi: 10.1007 / s000120050042

obwohl dies anscheinend früher veröffentlicht wurde:

  • Ágoston, I., Demetrovics, J. und Hannák, L. In Bezug auf die Anzahl der Klone, die alle Konstanten enthalten , beschreibt Coll. Mathematik. Soc. János Bolyai 43 21–25, 1983.

Eine nette spezifische Aussage stammt von:

  • A. Bulatov, A. Krokhin, K. Safin und E. Sukhanov, Zur Struktur von Klongittern , In: "Allgemeine Algebra und Diskrete Mathematik", Herausgeber: K. Denecke und O. Lueders, 27–34. Heldermann Verlag, Berlin, 1995. ( PS )

Folgerung 3 (Ágoston et al. Wie oben zugeschrieben): Sei . Dann beträgt die Anzahl der Klone in die alle Konstanten enthalten, .k3Lk20

Zum Abschluss sind mir keine Arbeiten zur Verwendung von nicht-booleschen Klonen für Schaltkreisuntergrenzen bekannt. Dies scheint es wert zu sein, eingehender untersucht zu werden. Angesichts der relativ geringen Kenntnis über das Klongitter gibt es möglicherweise interessante Operationsgrundlagen, die erst entdeckt werden müssen.

Weitere Verbindungen zwischen Klontheorie und Informatik wären wahrscheinlich auch für Mathematiker, die in der universellen Algebra arbeiten, von großem Interesse. Ein früheres Beispiel für diese Art von Interaktion kam zustande, als Peter Jeavons zeigte, dass Algebren mit Bedingungssprachen in Verbindung gebracht werden können, sodass Traktabilitätsergebnisse in Eigenschaften der Algebra übersetzt werden können. Andrei Bulatov hat dies genutzt, um die Dichotomie für CSPs mit der Domänengröße 3 zu beweisen. Andererseits hat das Interesse an der Theorie der zahmen Kongruenz infolge der Anwendung der Informatik wieder zugenommen. Ich frage mich, was sich aus einer Verbindung zwischen Klontheorie und nicht-boolescher Schaltungskomplexität ergeben würde.

András Salamon
quelle
Vielen Dank, András! Ich werde das Papier von Ágoston et al. wenn ich eine chance bekomme. In der Zwischenzeit habe ich die Liste der maximalen vorkompletten Klone eines 3-Elemente-Sets von Pantović et al. Papier, mit dem Sie verlinkt haben, und ich glaube nicht, dass eines davon Kandidaten für "neue" Schaltungsuntergrenzen sind. (Für einige von ihnen ergeben sich exponentielle Untergrenzen unmittelbar aus der monotonen Untergrenze von Razborov; für andere benötigen wir Untergrenzen für allgemeine Schaltkreise oder für lineare Schaltkreise.) Aber selbst im Fall von k = 3 sind Klone kleiner als die vorkompletten immer noch einen Blick wert.
Scott Aaronson
15

Dies wird aus den Kommentaren verschoben, wie Suresh vorgeschlagen hat.

Wenn Sie die Funktionen berücksichtigen , ist die Situation für lineare Gatter schwieriger, da das Argument counting zeigt, dass es Funktionen gibt, die zu berechnende Gatter, obwohl es keine expliziten Beispiele für eine Funktion gibt, die Schaltungen mit superlinearer Größe erfordert.f:0,1n0,1nΩ(n2log(n))

Bearbeiten. Mit dem Argument counting kann auch gezeigt werden, dass die meisten Funktionen für eine Konstante eine Komplexität haben, die größer als Wenn Sie also eine Funktion zufällig auswählen, erhalten Sie eine komplexe Funktion mit hoher Wahrscheinlichkeit.n2log(n)cc

Andererseits, wie Scott Aaronson in den Kommentaren ausführt, ist es nicht schwer, Kandidaten für lineare Transformationen zu finden, die XOR-Gatter (die Fourier-Transformation, die "Sierpinski-Dichtung" -Matrix erfordern sollten ... ), und Bram Cohen schlug eine Beispielfunktion vor, die XOR-Gatter erfordern sollte .Ω(nlogn)Ω(n3/2)

Edit 2. Das Haupthindernis ist, dass wir keine Methoden haben, um nichtlineare Untergrenzen zu beweisen, selbst für lineare Gatter, soweit ich weiß (für lineare Untergrenzen kann man die Gatterelimination verwenden, die sehr unwahrscheinlich ist, non zu geben lineare Grenzen). Obwohl es so aussieht, als müssten einige Methoden aus der linearen Algebra wirklich hilfreich sein. Es ist also nett, sich Kandidaten auszudenken, aber es sind trotzdem einige neue Methoden erforderlich.

Grigory Yaroslavtsev
quelle
11
  1. Tatsächlich gab es Versuche, untere Grenzen für Schaltkreise zu beweisen, die über größere Domänen als . Sagen wir, Tkachov [Vestnik von der Moskauer Universität, Nr. 1, 1977, in russischer Sprache] betrachtete Schaltungen, die mit Eingangsvektoren in . Als Tore erlaubte er und . Er betrachtete die folgende Funktion: wenn eine enthält oder die Zahl von in mindestens die Zahl von . Er zeigt, dass jede Schaltung (über diese MIN / XOR-Basis) ungefähr Gatter benötigt, um zu berechnen{0,1}aZ3n={0,1,2}nmin(x,y)xymod2f(a)=0a02a12n/nf. Aber das war es! Mir sind keine weiteren Ergebnisse bekannt, die zu einem ähnlichen Gefallen führen (zu größeren, aber immer noch endlichen Domänen), mit Ausnahme natürlich der Dinge, die mit arithmetischen Schaltkreisen zu tun haben. Aber nur für Schaltkreise - zum Verzweigen von Programmen zu größeren Domänen zu gehen, erleichtert die Aufgabe von Untergrenzen etwas.

  2. Auf Schaltungen mit XOR-Gattern. Hier ist sogar der Fall der Tiefe weithin offen. Die höchsten Untergrenzen für explizite lineare Transformationen über haben die Form . Es ist eine Herausforderung , eine Schranke wie für eine Konstante zu beweisen , auch in Tiefe und selbst wenn nur XOR-Gatter zulässig sind.2y=AxGF(2)nlog3/2nn1+cc>02

Stasys
quelle
2
Lieber Stasys, darf ich vorschlagen, dass Sie Ihr Konto registrieren ? Sie können unter anderem das gleiche Benutzerkonto verwenden, um Antworten zu posten und später zu bearbeiten. (Lassen Sie mich wissen, wenn Sie sich für eine Registrierung entscheiden, und ich werde Ihre vorherigen Konten damit zusammenführen, damit Sie auch Ihre vorherigen Beiträge bearbeiten können.)
Kaveh
1
Danke, Kaveh, ich habe mich gerade registriert. Scotts Vorschlag (zu größeren Domänen wechseln) kann auch aus "pragmatischer" Sicht interessant sein. Sagen wir, was ist die kleinste Anzahl von Max / Plus-Gattern in einer Schaltung für das Subset-Sum-Problem mit der Kapazität des Rucksacks ? Um den standardmäßigen dynamischen Programmieralgorithmus zu simulieren, ist es ausreichend, Drähte Tests für ganze Zahlen in unserer Domäne durchführen zu lassen. Dieser Algorithmus gibt auch eine obere Schranke für die Anzahl der Tore an. Problem: beweisen Sie, dass Tore notwendig sind. Dies würde bedeuten, dass DP nicht besser für Knapsack sein kann. Kxi=aanKΩ(nK)
Stasys