##  [Boolescher Schaltkreis](/de/node/58909) 

 Definition

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

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

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

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

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

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

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

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

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.