Komplexität der Konvertierung einer Booleschen Schaltung in eine Boolesche Formel

10

Was ist bei einer booleschen Schaltung für Variablen (die nur die Gatter NOT, AND und OR verwendet) der effizienteste Weg, um die durch die Schaltung dargestellte boolesche Formel zu extrahieren? Gibt es einen Polytime-Algorithmus für dieses Problem?Cn

Nikhil
quelle
Welche Art von Toren hat die Schaltung?
Lev Reyzin
1
Welche Einschränkungen beim Fan-In oder Fan-Out? Wenn es sich nur um ein einzelnes Fan-Out handelt, ist es trivial: Die Schaltung selbst ist im Wesentlichen ein AST für die Formel.
Mark Reitblatt
1
Eingeschränktes Fan-In, um allgemein zu sein. Um genau zu sein, sagen wir, UND und ODER haben Fan-In 2. In vielen Literaturstellen finde ich, dass eine Schaltung und Formeln austauschbar verwendet werden, aber ich möchte wissen, ob die Konvertierung einer Schaltung in eine Formel einfach ist Problem.
Nikhil
6
Im Allgemeinen würden Sie erwarten, dass jede äquivalente Formel selbst für eine kleine Schaltung eine exponentielle Größe haben könnte.
Kristoffer Arnsfelt Hansen
4
Polynomgrößenformeln entsprechen Schaltungen . Es ist nicht bekannt, dass Polysize-Schaltungen ( ) . Die Formeln und Schaltungen werden normalerweise austauschbar verwendet, wenn die Tiefe der Schaltung begrenzt ist. NC1 P/polyNC1
Kaveh

Antworten:

8

Wenn ich Ihre Frage richtig verstehe, würde ich sagen, dass Sie die Standardreduktion von CIRCUIT-SAT auf SAT verwenden könnten: Stellen Sie jedes Gate als neue Variable dar und stellen Sie dann die gesamte Schaltung in CNF-Form dar, wobei jede Klausel die Form , wobei die neue Variable ist und die Formel für das Gate durch , wobei die Variablen für andere Gates verwendet werden, um die Eingaben darzustellen. Dies kann durch einfaches Durchlaufen erfolgen (in linearer Zeit, was eindeutig optimal ist).(vϕ)vϕ

Wenn Sie beispielsweise drei Eingänge haben, , und , mit UND-Gattern, die und sowie und , und einem ODER-Gatter, das ihre Ausgänge verbindet, können Sie drei Variablen einführen, um die Gatter darzustellen - , bzw. - und schreiben Sie die Formel inBeachten Sie, dass die Ausgabevariable explizit enthalten ist.x1x2x3x1x2x2x3v1v2v3

(v1(x1x2))(v2(x2x3))(v3(v1v2))v3.

Einführung in Algorithmen von Cormen et al. erklärt dies ausführlich im Kapitel über NP-Vollständigkeit.

Magnus Lie Hetland
quelle
Verwendet CIRCUIT-SAT keine Fan-Out-1-Gates?
Mark Reitblatt
1
Sicher - aber soweit ich sehen kann, hat dies keinen Einfluss auf die Reduktion / Transformation. Die Idee, jeden Ausgang als neue Variable darzustellen, bedeutet, dass Sie jeden Ausgang mehrmals als Eingang wiederverwenden können (entsprechend einem beliebig großen Fan-Out). Mit anderen Worten, die in dieser Antwort angegebene Lösung sollte für beliebige Schaltungen funktionieren.
Magnus Lie Hetland
3
Ich würde vermuten, dass dies nicht das ist, wonach gefragt wird. Ich denke, was gewünscht wird, ist eine Formel auf dem gleichen Satz von Variablen wie die Schaltung zu machen.
Kristoffer Arnsfelt Hansen
1
Hm. Ja, du hast wahrscheinlich recht. Die Einführung der neuen Variablen ist im Fall CIRCUIT-SAT zu CNF-SAT sinnvoll, jedoch nicht in einer allgemeineren Umgebung - da stimme ich zu.
Magnus Lie Hetland
1
@Kristoffer: Ich meinte genau das, was du gesagt hast. Wenn eine Schaltung auf möchte ich, dass die Formel der exakte boolesche Ausdruck für die Schaltung ist. x 1 , x 2 , , x n ϕ ( x 1 , x 2 , , x n )Cx1,x2,,xnϕ(x1,x2,,xn)
Nikhil