Complexité de la conversion d'un circuit booléen en formule booléenne

Étant donné un circuit booléen sur variables (qui utilise uniquement les portes NON, ET et OU), quelle est la manière la plus efficace d'extraire la formule booléenne représentée par le circuit? Existe-t-il un algorithme de polytime pour ce problème? $C$ $n$

cc.complexity-theory time-complexity boolean-functions Nikhil
la source

quel type de portes le circuit a-t-il?

Lev Reyzin

Quelles restrictions sur le fan-in ou le fan-out? S'il ne s'agit que d'un simple fan-out, c'est trivial: le circuit lui-même est essentiellement un AST pour la formule.

Mark Reitblatt

Fan-in borné pour être général. Mais pour être précis, disons que ET et OU ont un fan-in 2. Dans de nombreuses références dans la littérature, je trouve qu'un circuit et des formules sont utilisés de manière interchangeable, mais je veux savoir si la conversion d'un circuit en une formule est facile problème.

Nikhil

En général, vous vous attendez à ce que toute formule équivalente puisse être de taille exponentielle même pour un petit circuit.

Kristoffer Arnsfelt Hansen

Les formules de taille polynomiale sont équivalentes à

N C^{1}

$NC^1$ circuits

. Les circuits de polysize (

P / p o l y

$P/poly$ ) ne sont pas connus pour être équivalents à

N C^{1}

$NC^1$ . Les formules et les circuits sont utilisés de manière interchangeable généralement lorsque la profondeur du circuit est limitée.

Kaveh

Réponses:

Si je comprends bien votre question, je dirais que vous pouvez utiliser la réduction standard de CIRCUIT-SAT à SAT: Représentez chaque porte comme une nouvelle variable, puis représentez l'ensemble du circuit sous forme CNF, chaque clause ayant la forme , où est la nouvelle variable, et la formule de la porte est donnée par , en utilisant les variables pour d'autres portes pour représenter les entrées. Cela peut se faire par une simple traversée (en temps linéaire, ce qui est clairement optimal). $(v\leftrightarrow\phi)$ $v$ $\phi$

Par exemple, si vous avez trois entrées, , et , avec des portes ET reliant et ainsi que et , et une porte OU reliant leurs sorties, vous pouvez introduire trois variables pour représenter les portes - , et , respectivement - et réécrire la formule en $x_1$ $x_2$ $x_3$ $x_1$ $x_2$ $x_2$ $x_3$ $v_1$ $v_2$ $v_3$ Notez que la variable de sortie est incluse explicitement.

(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\,.$

Introduction aux algorithmes par Cormen et al. explique cela en détail, dans le chapitre sur NP-Completeness.

Magnus Lie Hetland
la source

CIRCUIT-SAT n'utilise-t-il pas de portes de dérivation 1?

Mark Reitblatt

Bien sûr, mais pour autant que je puisse voir, cela n'affecte pas la réduction / transformation. L'idée de représenter chaque sortie comme une nouvelle variable signifie que vous pouvez réutiliser chaque sortie comme entrée plusieurs fois (correspondant à un fan-out arbitrairement grand). En d'autres termes, la solution donnée dans cette réponse devrait fonctionner pour des circuits arbitraires.

Magnus Lie Hetland

Je suppose que ce n'est pas ce qui est demandé. Je pense que ce que l'on veut, c'est faire une formule sur le même ensemble de variables que le circuit.

Kristoffer Arnsfelt Hansen

Hm. Oui, vous avez probablement raison. L'introduction des nouvelles variables est logique dans le cas CIRCUIT-SAT à CNF-SAT, mais pas dans un cadre plus général - je suis d'accord.

Magnus Lie Hetland

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)$