Sind UND- und ODER-Kreise P-vollständig?

Das AND & OR-Gatter ist ein Gatter, das zwei Eingänge erhält und deren AND und deren OR zurückgibt. Können Schaltungen, die nur aus dem AND & OR-Gatter bestehen, ohne Fanout willkürliche Berechnungen durchführen? Genauer gesagt, ist der Lograum für die Polynomzeitberechnung auf UND- und ODER-Schaltungen reduzierbar?

Meine Motivation für dieses Problem ist ziemlich seltsam. Wie hier beschrieben , ist diese Frage wichtig für die Berechnung im Computerspiel Dwarf Fortress .

Wenn ich nicht falsch verstehen , was meinen Sie mit UND , ODER - Gatter, es ist im Grunde ein Komparator - Gatter, das zwei Eingangsbits nimmt und y und erzeugt zwei Ausgangsbits x ∧ y und x ∨ y . Die zwei Ausgangsbits x ∧ y und x ∨ y sind im Grunde genommen min ( x , y ) und max ( x , y ) .$x$$y$$x\wedge y$$x\vee y$$x\wedge y$$x\vee y$$(x,y)$$(x,y)$

Komparatorschaltungen werden aufgebaut, indem diese Komparatorgatter zusammengesetzt werden, jedoch keine weiteren Fan-Outs als die beiden von jedem Gatter erzeugten Ausgänge zugelassen werden . Daher können wir Komparatorschaltungen mit den folgenden Notationen zeichnen (ähnlich wie wir Sortiernetzwerke zeichnen).

Wir können das Comparator Circuit Value Problem (CCV) wie folgt definieren: Bestimmen Sie bei einer Komparatorschaltung mit festgelegten booleschen Eingängen den Ausgangswert einer bestimmten Leitung. Indem wir dieses CCV-Problem unter Reduzierung des logarithmischen Bereichs schließen, erhalten wir die Komplexitätsklasse CC , deren vollständige Probleme natürliche Probleme wie Lex-First Maximum Matching, stabile Heirat und stabile Mitbewohner umfassen.

$^0$$\subseteq$$\subseteq$

(Die Antwort ist nicht zulässig, da sie sich auf separate UND-, ODER-Gatter ohne Auffächerungsbeschränkung bezieht.)

Der folgende Artikel befasst sich mit folgenden Themen: Mehrheitsabstimmungs-Zellularautomaten, Ising-Dynamik und P-Vollständigkeit

Wir zeigen, dass diese Systeme in drei oder mehr Dimensionen Boolesche Schaltkreise von UND- und ODER-Gattern simulieren können und daher P-vollständig sind . Das heißt, die Vorhersage ihres Zustands in Zeitschritten in der Zukunft ist mindestens so schwierig wie jedes andere Problem, das auf einem seriellen Computer polynomielle Zeit benötigt.

(...)

Das Monotone Circuit Value-Problem, bei dem UND- und ODER-Gatter zulässig sind, NICHT-Gatter jedoch nicht, ist aus folgendem Grund immer noch P-vollständig: Mit De Morgans Gesetzen (...) können wir Negationen durch die Gatter zurückschieben, bis sie nur noch vorhanden sind wirken sich auf die Eingänge selbst aus. Somit kann jedes Problem mit dem Schaltkreiswert in ein Problem mit dem monotonen Schaltkreiswert umgewandelt werden, wobei einige der Eingänge negiert werden. Diese Art der Konvertierung von einer Instanz eines Problems zu einer Instanz eines anderen wird als Reduktion bezeichnet.