Benutzer:PlatinIridium/Schaltkreiskomplexität
Die Schlatkreiskomplexität ist ein Teilgebiet der Komplexitätstheorie und befasst sich damit mit der Komplexität algorithmisch berechenbarer Probleme. Dabei liegt der Fokus auf "Parallelisierbarkeit" von Problemen. Zum Vergleich von Problemen betrachtet man hier aber weder Zeit noch Speicherplatz als Maße, sondern Berechnungsmodell betrachtet man jedoch Schaltkreise, genauer gesagt Schaltkreisfamilien, als B Anders als in ande und der Schaltkreiskomplexität, ist AC eine Komplexitätsklasse und ACi eine Hierarchie von Komplexitätsklassen. Für jedes {\displaystyle i\in \mathbb {N} }
enthält ACi die formalen Sprachen, die von Schaltkreisfamilien mit Tiefe
{\displaystyle O(\log ^{i}n)} , polynomieller Größe, und Und- und Oder- mit unbeschränktem Fan-In und eventuell Nicht-Gattern an den Eingängen erkannt werden. Die Klasse AC ist dann definiert als
Schaltkreise und Schaltkreisfamilien
Ein Schaltkreis ist ...
Ähnlich wie andere Berechnnungsmodelle wie zum Beispiel Turingmaschinen, sind Schaltkreise nicht aussließlich zur Berechnung von Entscheidungsproblemen geeignet, da Sie mehrere Ausgabergatter haben können. Das Problem von Schaltkreisen ist jedoch, dass sie nur eine feste Anzahl an Ein- und Ausgabegattern besitzen. Somit könnte man im Falle von Schaltkreisen nur Eingaben einer festen Länge betrachten. Aus diesem Grund betrachtet man in der Schaltkreiskomplexität daher Schaltkreisfamilien als Mengen von Schaltkreise, die für jede mögliche Eingabelänge einen Schaltkreis enthalten.
Eine Schaltkreisfamilie ist eine Familie $(C_n)_{n\in\mathbb{N}}$ von Schaltkreisen, die für jede mögliche Eingabelänge $n$ einen Schaltkreis .
Während
Uniforme Schaltkreisfamilien
Theoretisch ist es möglich jedes Problem, also auch unentscheidbare Probleme wie das Halteproblem mit Schaltkreisfamilien zu entscheiden: Für jede Eingabelänge $n$ gibt es in jeder Sprache nur endlich positive Instanzen. Diese kann man also fest in einer endlichen Wertetabelle beschreiben, die sich direkt in einem endlich großen Schaltkreis kodieren lässt. Also gibt es für jedes $n$ und jedes Problem $P$ einen Schaltkreis $C_n$ der $P\cap\{0,1\}^n$ korrekt entscheidet. Damit existiert dann aber auch eine Schaltkreisfamilie. Es ist nur möglich und im Falle des Halteproblems der Fall, dass für ein gegebenes $n$ der Schaltkreis selbst nicht berechenbar ist. Daher schränkt man in der Regel schaltkreisfamilien weiter ein, auch um dann sinnvolle neue Komplexitätsklassen erhalten zu können. Dazu beschränkt man sich meist auf uniforme Schaltkreisfamilien und fordert zum Beispiel, dass jeder Schaltkreis $C_n$ einer Schaltkreisfamilie $C$ aus der Eingabelänge $n$ von einer Turingmaschine berechenbar sein muss. Es kann aber auch stärkere Einschränkungen wie polynomielle Laufzeit oder logarithmischen Speicherplatz geben. Schaltkreisfamilien ohne jegliche Einschränkungen nennt man nichtuniform.
Komplexitätsklassen in der Schaltkreiskomplexität Schaltkreisgröße
Die Größe eines Schaltkreises ist die Anzahl alles Gatter und die Länge des längsten Pfades von einem Eingangsgatter zu einem Ausgangsgatter ist die Schaltkreises.
NC-Hierarchie
AC-Hierarchie
