Komplexität der Schaltung

Beispiel Boolean Circuit. Das ${\ displayStyle \ Wedge}$ Knoten sind Und Tore, das ${\ displayStyle \ vee}$ Knoten sind Oder Tore, und die ${\ displayStyle \ neg}$ Knoten sind Keine Tore

Im Theoretische Informatik, Komplexität der Schaltung ist ein Zweig von Computerkomplexitätstheorie in welchem Boolesche Funktionen werden gemäß der Größe oder Tiefe des Boolesche Schaltungen das berechnet sie. Ein verwandter Begriff ist die Schaltungskomplexität von a rekursive Sprache das ist beschlossen durch eine Uniform Familie von Schaltungen ${\ displayStyle c_ {1}, c_ {2}, \ ldots}$ (siehe unten).

Das Nachweis der unteren Grenzen der Größe des Booleschen Schaltkreise, die explizite boolesche Funktionen berechnen, ist ein beliebter Ansatz zur Trennung von Komplexitätsklassen. Zum Beispiel a prominent Schaltungsklasse P/poly besteht aus Booleschen Funktionen, die durch Schaltkreise der Polynomgröße berechnet werden können. Das beweisen ${\ displaystyle {\ mathsf {np}} \ nicht \ subseteq {\ mathsf {p/poly}}}$ würde trennen P und Np (siehe unten).

Komplexitätsklassen In Bezug auf die Booleschen Schaltungen definiert AC⁰, AC, TC⁰, NC¹, NC, und P/poly.

Größe und Tiefe

Eine boolesche Schaltung mit ${\ displayStyle n}$ Eingang Bits ist ein Regie acyclische Graphen in dem jeder Knoten (normalerweise genannt Tore in diesem Zusammenhang) ist entweder ein Eingangsknoten von in Grad 0 gekennzeichnet von einem der ${\ displayStyle n}$ Eingangsbits, an Und Tor, ein Oder Tor, oder ein Kein Tor. Eines dieser Tore ist als Ausgangstor bezeichnet. Eine solche Schaltung berechnet natürlich eine Funktion seiner ${\ displayStyle n}$ Eingänge. Die Größe einer Schaltung ist die Anzahl der Gates, die sie enthält, und ihre Tiefe ist die maximale Länge eines Pfades von einem Eingangstor zum Ausgangstor.

Es gibt zwei Hauptvorstellungen von Kreislaufkomplexität^[1] Das Komplexität der Schaltungsgröße einer Booleschen Funktion ${\ displayStyle f}$ ist die minimale Größe eines Schaltungscomputings ${\ displayStyle f}$. Das Komplexität des Schaltungstiefens einer Booleschen Funktion ${\ displayStyle f}$ ist die minimale Tiefe eines Schaltungscomputings ${\ displayStyle f}$.

Diese Begriffe verallgemeinern, wenn man die Kreiskomplexität einer Sprache berücksichtigt, die Zeichenfolgen mit unterschiedlichen Bitlängen enthält, insbesondere unendlich formelle Sprachen. Boolesche Schaltungen ermöglichen jedoch nur eine feste Anzahl von Eingangsbits. Daher kann kein einzelner Boolesche Schaltung eine solche Sprache entscheiden. Um diese Möglichkeit zu berücksichtigen, betrachtet man Familien von Schaltungen ${\ displayStyle c_ {1}, c_ {2}, \ ldots}$ wo jeweils ${\ displayStyle c_ {n}}$ Akzeptiert Eingaben der Größe ${\ displayStyle n}$. Jede Schaltkreisfamilie erzeugt die Sprache natürlich per Schaltung ${\ displayStyle c_ {n}}$ Ausgang ${\ displayStyle 1}$ Wenn eine Länge ${\ displayStyle n}$ String ist ein Familienmitglied und ${\ displayStyle 0}$ Andernfalls. Wir sagen, dass eine Familie von Schaltungen ist Größe minimal Wenn es keine andere Familie gibt, die sich für Eingaben einer Größe entscheidet, ${\ displayStyle n}$, mit einer Schaltung von kleinerer Größe als ${\ displayStyle c_ {n}}$ (jeweils für Tiefe minimal Familien). Somit ist die Komplexität der Schaltung auch für sinnvoll Nicht rekursive Sprachen. Die Vorstellung von a einheitliche Familie Ermöglicht Varianten der Schaltungskomplexität, die mit Algorithmusbasis -Komplexitätsmessungen rekursiver Sprachen zusammenhängen. Die ungleichmäßige Variante ist jedoch hilfreich, um unter den unteren Grenzen zu finden, wie komplex jede Schaltkreisfamilie sein muss, um die angegebenen Sprachen zu entscheiden.

Daher die Komplexität der Schaltungsgröße einer formalen Sprache ${\ displayStyle a}$ ist definiert als die Funktion ${\ displayStyle t: \ mathbb {n} \ to \ mathbb {n}}$, das bezieht sich ein bisschen Länge eines Eingangs, ${\ displayStyle n}$, zur Komplexität der Schaltungsgröße eines Minimalkreislaufs ${\ displayStyle c_ {n}}$ Das entscheidet, ob Eingänge dieser Länge in der Länge sind ${\ displayStyle a}$. Das Komplexität des Schaltungstiefens ist ähnlich definiert.

Gleichmäßigkeit

Boolesche Schaltungen sind eines der Hauptbeispiele für sogenannte ungleichmäßige Berechnungsmodelle in dem Sinne, dass Eingänge unterschiedlicher Längen durch verschiedene Schaltungen verarbeitet werden, im Gegensatz zu gleichmäßigen Modellen wie z. Turing -Maschinen wobei das gleiche Rechengerät für alle möglichen Eingangslängen verwendet wird. Ein Individuum Rechenproblem ist daher mit einem bestimmten verbunden Familie von Booleschen Schaltungen ${\ displayStyle c_ {1}, c_ {2}, \ dots}$ wo jeweils ${\ displayStyle c_ {n}}$ Ist die Schaltungshandhabung Eingänge von n Bits. EIN Gleichmäßigkeit Bedingung wird diesen Familien häufig auferlegt, was die Existenz einiger möglicherweise erfordert ressourcengebunden Turing -Maschine, die bei Eingabe nerzeugt eine Beschreibung der einzelnen Schaltung ${\ displayStyle c_ {n}}$. Wenn diese Turing -Maschine eine Laufzeitpolynom in hat nDie Kreisleiterfamilie soll p-uniform sein. Die strengere Anforderung von Dlogime-Einheitlich ist von besonderem Interesse an der Untersuchung von Schaltungsklassen mit flachem Tiefen wie AC⁰ oder tc⁰. Wenn keine Ressourcengrenzen angegeben sind, ist eine Sprache rekursiv (d. H. Von einer Turing -Maschine enttäuscht), wenn die Sprache von einer einheitlichen Familie von Booleschen Schaltungen entschieden wird.

Polynomzeituniform

Eine Familie von Booleschen Schaltungen ${\ displaystyle \ {c_ {n}: n \ in \ mathbb {n} \}}$ ist Polynomzeituniform Wenn es vorhanden ist a deterministische Turing -Maschine M, so dass

• M läuft in Polynomzeit
• Für alle ${\ displayStyle n \ in \ mathbb {n}}$, M gibt eine Beschreibung von aus ${\ displayStyle c_ {n}}$ auf Eingabe ${\ displayStyle 1^{n}}$

Logspace -Uniform

Eine Familie von Booleschen Schaltungen ${\ displaystyle \ {c_ {n}: n \ in \ mathbb {n} \}}$ ist Logspace -Uniform Wenn es vorhanden ist a deterministische Turing -Maschine M, so dass

• M läuft im logarithmischen Raum
• Für alle ${\ displayStyle n \ in \ mathbb {n}}$, M gibt eine Beschreibung von aus ${\ displayStyle c_ {n}}$ auf Eingabe ${\ displayStyle 1^{n}}$

Geschichte

Die Komplexität der Schaltung geht zurück zu Shannon 1949,^[2] Wer hat bewiesen, dass fast alle booleschen Funktionen auf n Variablen erfordern Schaltungen der Größe θ (2ⁿ/n). Trotz dieser Tatsache konnten die Komplexitätstheoretiker bisher keine superlineare Untergrenze für eine explizite Funktion erweisen.

Unter bestimmten Einschränkungen der verwendeten Schaltkreise wurden unter bestimmten Einschränkungen der Familie der Kreisläufe nachgewiesen. Die erste Funktion, für die superpolynomiale Schaltkreis unteren Grenzen gezeigt wurden, war die Paritätsfunktion, was die Summe seines Eingangsbits Modulo 2. Die Tatsache berechnet, dass Parität nicht in enthalten ist AC⁰ wurde erstmals 1983 von Ajtai unabhängig gegründet^[3][4] und von Furst, Saxe und Sipser im Jahr 1984.^[5] Spätere Verbesserungen durch Håstad 1987^[6] Es wurde festgestellt, dass jede Familie von Schaltkreisen mit konstantem Tiefen die Paritätsfunktion eine exponentielle Größe erfordert. Ein Ergebnis von Razborov, das Ergebnis von Razborov,^[7] Smolensky im Jahr 1987^[8] bewiesen, dass dies zutrifft, auch wenn die Schaltung mit Gates verstärkt wird, die die Summe ihrer Eingangsbits Modulo einige seltsame Primes berechnen p.

Das k-Clique Problem Es ist zu entscheiden, ob eine bestimmte Grafik auf n Scheitelpunkte haben eine Größe der Größe k. Für eine bestimmte Wahl der Konstanten n und kDas Diagramm kann in Binärdatei mit Verwendung kodiert werden ${\ displayStyle {n \ wählen Sie 2}}$ Bits, die für jede mögliche Kante zeigen, ob sie vorhanden ist. Dann ist die k-Clique -Problem wird als Funktion formalisiert ${\ displayStyle f_ {k}: \ {0,1 \}^{n \ wählen 2} \ to \ {0,1 \}}$ so dass ${\ displayStyle f_ {k}}$ Ausgibt 1, wenn und nur wenn der von der Zeichenfolge codierte Diagramm eine Größe der Größe enthält k. Diese Funktionsfamilie ist monoton und kann von einer Familie von Schaltungen berechnet werden. Es wurde jedoch gezeigt, dass sie nicht von einer polynomialen Familie von monotonischen Schaltungen berechnet werden kann (dh Schaltungen mit und und und oder ohne Negation). Das ursprüngliche Ergebnis von Razborov 1985^[7] wurde später 1987 zu einer von Alon und Boppana von Alon und Boppana unteren exponentiellen Größe verbessert.^[9] Im Jahr 2008 Rossman^[10] zeigten, dass die Schaltkreise konstanter Tiefe mit und oder, und nicht Toren Größe erfordern ${\ displayStyle \ Omega (n^{k/4})}$ um die zu lösen k-Clique Problem auch in der Durchschnittlicher Fall. Darüber hinaus gibt es eine Größe der Größe ${\ displayStyle n^{k/4+o (1)}}$ das berechnet ${\ displayStyle f_ {k}}$.

Im Jahr 1999, Raz und McKenzie zeigte später, dass die monotone NC -Hierarchie unendlich ist.^[11]

Das Ganzzahl -Division -Problem liegt in Uniform TC⁰.^[12]

Schaltkreis Untergrenzen

Die unteren Grenzen der Schaltkreise sind im Allgemeinen schwierig. Bekannte Ergebnisse umfassen

• Parität ist nicht ungleichmäßig AC⁰, bewiesen von Ajtai im Jahr 1983^[3][4] sowie von Furst, Saxe und Sipser im Jahr 1984.^[5]
• Uniform TC⁰ ist streng enthalten in Pp, bewiesen von Allender.^[13]
• Die Klassen S^P
  ₂, Pp^{[NB 1]} und Ma/1^[14] (MA mit einem bisschen Rat) sind nicht in GRÖSSE(n^k) für jede Konstante k.
• Während der Verdacht wird, dass die ungleichmäßige Klasse Acc⁰ Enthält nicht die Mehrheitsfunktion, es war erst 2010 das Williams geprüft, dass $oder$.^[15]

Es ist offen, ob Nexptime ungleichmäßiges TC hat⁰ Schaltungen.

Beweise der unteren Grenzen des Schaltungskreislaufs sind stark an verbunden mit Derandomisierung. Ein Beweis dafür ${\ displaystyle {\ mathsf {p}} = {\ mathsf {bpp}}}$ würde das auch implizieren ${\ displaystyle {\ mathsf {nexp}} \ nicht \ subseteq {\ mathsf {p/poly}}}$ oder dass dauerhaft nicht durch ungleichmäßige arithmetische Schaltungen (Polynome) von Polynomgröße und Polynomgrad berechnet werden kann.^[16]

Im Jahr 1997 zeigten Razborov und Rudich, dass viele bekannte Schaltkreis unteren Grenzen für explizite Boolesche Funktionen die Existenz von sogenannten bedeuten natürliche Eigenschaften Nützlich gegen die jeweilige Schaltungsklasse.^[17] Andererseits würden natürliche Eigenschaften, die gegen P/Poly nützlich sind, starke Pseudorandomgeneratoren brechen. Dies wird oft als "natürliche Beweise" -Barriere für den Nachweis einer starken Kreislaufgrenzen interpretiert. Im Jahr 2016 bewiesen Carmosino, Impagliazzo, Kabanets und Kolokolova, dass natürliche Eigenschaften auch zum Konstruktion effizienter Lernalgorithmen verwendet werden können.^[18]

Komplexitätsklassen

Viele Schaltungskomplexitätsklassen sind in Bezug auf Klassenhierarchien definiert. Für jede nicht negative Ganzzahl i, Es gibt eine Klasse NCⁱ, bestehend aus Tiefenschaltungen in Polynomgröße ${\ displayStyle o (\ log ^{i} (n))}$, mit begrenztem Fan-in und, oder und nicht und nicht Toren. Der Union NC aller dieser Klassen ist ein Thema der Diskussion. Durch die Berücksichtigung von unbegrenzten Fan-in-Toren die Klassen ACⁱ und AC (was gleich NC ist) kann konstruiert werden. Viele andere Schaltungskomplexitätsklassen mit gleicher Größe und Tiefenbeschränkungen können konstruiert werden, indem verschiedene Gatesätze ermöglicht werden.

Beziehung zur Zeitkomplexität

Wenn eine bestimmte Sprache, ${\ displayStyle a}$, gehört zum Zeitkomplexitätsklasse ${\ displayStyle {\ text {time}} (t (n))}$ für eine gewisse Funktion ${\ displayStyle t: \ mathbb {n} \ to \ mathbb {n}}$, dann ${\ displayStyle a}$ hat Schaltungskomplexität ${\ displayStyle {\ mathcal {o}} (t (n) \ log t (n))}$. Wenn die Turing -Maschine, die die Sprache akzeptiert nicht bewusst (was bedeutet, dass es unabhängig von der Eingabe die gleichen Gedächtniszellen liest und schreibt) dann ${\ displayStyle a}$ hat Schaltungskomplexität ${\ displayStyle {\ mathcal {o}} (t (n))}$.^[19]

Siehe auch

• Schaltungsminimierung

Anmerkungen

Verweise

Weitere Lektüre

• Vollmer, Heribert (1999). Einführung in die Komplexität der Schaltung: Ein einheitlicher Ansatz.Texte in theoretischer Informatik.Eine EATCS -Serie. Springer Verlag. ISBN 978-3-540-64310-4.
• Wegener, Ingo (1987) [November 1986]. Die Komplexität der Booleschen Funktionen.Wiley -Teubner -Serie in Computerwissenschaften.Frankfurt am Main/Bielefeld, Deutschland: John Wiley & Sons Ltd., und B. G. Teubner Verlag, Stuttgart. ISBN 3-519-02107-2. Lccn 87-10388. (xii+457 Seiten) (nb. Zu der Zeit ein einflussreiches Lehrbuch zu diesem Thema, allgemein bekannt als "Blue Book". Auch verfügbar für PDF Herunterladen) Bei der Elektronisches Kolloquium zur Rechenkomplexität.))
• Zwick, Uri. "Vorlesungen für einen Kurs von Uri Zwick über die Komplexität der Schaltung".