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

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? $C$ $n$

cc.complexity-theory time-complexity boolean-functions Nikhil
quelle

Welche Art von Toren hat die Schaltung?

Lev Reyzin

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

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

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

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.

N C^{1}

$NC^1$

P / p o l y

$P/poly$

N C^{1}

$NC^1$

Kaveh

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\leftrightarrow\phi)$ $v$ $\phi$

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. $x_1$ $x_2$ $x_3$ $x_1$ $x_2$ $x_2$ $x_3$ $v_1$ $v_2$ $v_3$

(v_{1} \leftrightarrow (x_{1} \land x_{2})) \land (v_{2} \leftrightarrow (x_{2} \land x_{3})) \land (v_{3} \leftrightarrow (v_{1} \lor v_{2})) \land v_{3} .

$(v_1\leftrightarrow(x_1\land x_2))\land (v_2\leftrightarrow(x_2\land x_3))\land (v_3\leftrightarrow(v_1\lor v_2))\land v_3\,.$

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

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

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

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

@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.

C

$C$

x_{1}, x_{2}, \dots, x_{n}

$x_1, x_2, \ldots, x_n$

ϕ (x_{1}, x_{2}, \dots, x_{n})

$\phi(x_1, x_2, \ldots, x_n)$

Nikhil

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

Antworten: