Boolesche Schaltkreise und Schaltkreiskomplexität

Boolesche Schaltkreise berechnen Funktionen über Netzwerke von Logikgattern, und die Schaltkreiskomplexität misst Probleme anhand der Größe und Tiefe der zur Lösung benötigten Schaltkreise, was eine parallele und hardwareorientierte Sichtweise der Berechnung bietet.

Definition

Ein Boolescher Schaltkreis ist ein gerichteter azyklischer Graph von Logikgattern, der eine Funktion von binären Eingaben fester Länge berechnet; die Schaltkreiskomplexität untersucht die minimale Anzahl von Gattern, die Tiefe oder andere strukturelle Ressourcen, die zur Berechnung einer gegebenen Familie Boolescher Funktionen erforderlich sind.

Scope

Dieses Thema behandelt Boolesche Schaltkreise und Formeln, die Größen- und Tiefenmaße der Komplexität, uniforme versus nicht-uniforme Modelle, Klassen geringer Tiefe wie NC und AC, die Beziehung zwischen Schaltkreis-Untergrenzen und der Trennung von Komplexitätsklassen sowie wegweisende Untergrenzen-Ergebnisse für eingeschränkte Schaltkreisfamilien.

Core questions

• Wie unterscheidet sich die Gatter-Netzwerk-Sichtweise der Berechnung von sequenziellen Maschinen?
• Was messen Schaltkreisgröße und -tiefe, und wie stehen sie in Beziehung zu Zeit und Parallelität?
• Warum sind Schaltkreis-Untergrenzen ein Weg zur Trennung von Komplexitätsklassen?
• Welche Untergrenzen sind bekannt, und welche Barrieren blockieren stärkere?

Key theories

Nicht-Uniformität und die Klasse P/poly

Schaltkreise erlauben für jede Eingabelänge eine andere Maschine, was die nicht-uniforme Klasse P/poly ergibt, die P enthält; der Nachweis, dass ein NP-vollständiges Problem keine Schaltkreise polynomialer Größe besitzt, würde P von NP trennen und motiviert Schaltkreis-Untergrenzen.

Untergrenzen für eingeschränkte Schaltkreise

Starke Untergrenzen sind für begrenzte Familien bekannt, wie die exponentielle Größe, die für Schaltkreise konstanter Tiefe zur Berechnung der Parität erforderlich ist, auch wenn Untergrenzen für allgemeine Schaltkreise unerreichbar bleiben.

Clinical relevance

Schaltkreise sind das natürliche Modell digitaler Hardware, daher beeinflusst die Schaltkreiskomplexität das Chipdesign und die Grenzen paralleler Berechnungen; die Klassen geringer Tiefe erfassen, was mit vielen Prozessoren schnell berechnet werden kann, und Schaltkreis-Untergrenzen sind eine Hauptstrategie bei den langfristigen Bemühungen, Fragen wie P versus NP zu lösen.

History

Shannon verband 1937 die Boolesche Algebra mit Schaltkreisen, und die Schaltkreiskomplexität entwickelte sich in den 1980er Jahren zu einer Disziplin, als Furst, Saxe, Sipser und andere Untergrenzen konstanter Tiefe für Parität bewiesen und Razborov und Smolensky algebraische Methoden entwickelten, bevor die Natural-Proofs-Barriere aufzeigte, warum allgemeine Untergrenzen so schwer zu erreichen sind.

Key figures

• Claude Shannon
• Alexander Razborov
• Andrew Yao
• Roman Smolensky

Seminal works

• aroraBarak2009
• vollmer1999

Frequently asked questions

Wie unterscheiden sich Schaltkreise von Turingmaschinen?

Eine Turingmaschine ist ein einzelnes Gerät, das Eingaben aller Größen Schritt für Schritt verarbeitet, während ein Schaltkreis ein festes Netzwerk von Gattern für eine Eingabelänge ist, mit einem separaten Schaltkreis für jede Länge. Diese Nicht-Uniformität macht Schaltkreise zu einem natürlichen Modell für Hardware und parallele Berechnungen und kann Dinge ausdrücken, die keine einzelne uniforme Maschine kann.

Warum interessieren sich Forscher für Schaltkreis-Untergrenzen?

Der Nachweis, dass ein Problem in NP sehr große Schaltkreise erfordert, würde Komplexitätsklassen trennen und könnte P versus NP lösen. Untergrenzen sind für eingeschränkte Schaltkreisfamilien bekannt, aber ihre Erweiterung auf allgemeine Schaltkreise wird durch formale Barrieren blockiert, was dies zu einer der tiefsten offenen Herausforderungen in diesem Bereich macht.