Ein gerichteter azyklischer Netz von booleschen Logikgattern (AND, OR, NOT, etc.), verbunden durch Drähte, das boolesche Funktionen von Eingangs-Bits zu Ausgangs-Bits berechnet; verwendet als nicht-uniformes Berechnungsmodell, bei dem jede Eingabegröße ihren eigenen Schaltkreis hat.

Prinzip

Berechne eine boolesche Funktion durch das Zusammensetzen kleiner, fester logischer Primitive in einem azyklischen Graphen, sodass Ausgänge deterministische boolesche Kombinationen der Eingänge sind; Komplexität wird durch Größe (Anzahl Gatter) und Tiefe (längster Pfad) gemessen.

Demonstration

Für eine feste Eingabelänge n entwirf einen Schaltkreis, der Parität berechnet, indem Eingabebits paarweise in einem ausgeglichenen binären Baum von XOR-Gattern verXORt werden; analysiere die Tiefe als O(log n) und die Größe als O(n).

Fehlanwendung

Einen einzelnen Schaltkreis als uniforme algorithmische Beschreibung für alle Eingabegrößen zu behandeln, ohne eine Schaltkreisfamilie anzugeben, oder willkürliche Fan-in/Fan-out ohne Kosten anzunehmen, was irreführende Komplexitätsaussagen erzeugt.

Konsequenz

Bietet ein konkretes Modell, basierend auf Größe und Tiefe, für nicht-uniforme Komplexitätsklassen (z. B. P/poly) und Einsichten in hardwaremäßige Realisierbarkeit; Tiefe korreliert mit paralleler Zeit, Größe mit Ressourcenaufwand.

Umkehrung

Ein sequentielles, uniformes Modell wie die Turingmaschine oder RAM beschreibt ein einzelnes algorithmisches Verfahren, das für alle Eingabegrößen mittels eines endlichen Programms funktioniert und damit die nicht-uniforme Sichtweise umkehrt.

Abgrenzung

Geht von boolescher Logik und Azyklizität aus; schließt sequentielle Schaltungen mit Speicher aus, sofern sie nicht um Register erweitert werden; Kostenmodelle variieren bezüglich Fan-in, Fan-out und Gattertypen; erfasst keine probabilistischen oder quantenmechanischen Gatter ohne explizite Erweiterung.

Semantische Spannung

Ähnlich zu Formeln (baumförmige Schaltkreise) und Entscheidungsprogrammen; Spannung besteht zwischen Schaltkreisfamilien (nicht-uniform) und uniformen algorithmischen Modellen, bei denen sich eine einzige Beschreibung mit Eingabegröße skalieren muss.

Synthese

Eine statische, azyklische Komposition boolescher Gatter, parametrisiert durch Eingabegröße, die Eingabebits deterministisch auf Ausgänge abbildet; die Messung von Größe und Tiefe liefert Einsichten zu nicht-uniformen und parallelen Rechenressourcen.