Schaltungsuntergrenzen über beliebige Sätze von Toren

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} ⁿ → {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!

(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 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, .$k \ge 3$$\mathcal{L}_k$$2^{\aleph_0}$

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.

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,1}^n \rightarrow {0,1}^n$$\Omega(\frac{n^2}{\log(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.$\frac{n^2}{\log(n) * c}$$c$

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 .$\Omega(n log n)$$\Omega(n^{3/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.

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\}$$a$$Z_3^n=\{0,1,2\}^n$$\min(x,y)$$xy\mod{2}$$f(a)=0$$a$$0$$2$$a$$1$$2^n/\sqrt{n}$$f$. 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.$2$$y=Ax$$GF(2)$$n\log^{3/2}n$$n^{1+c}$$c>0$$2$