Complejidad de convertir un circuito booleano en una fórmula booleana

Dado un circuito booleano en variables (que usa solo compuertas NOT, AND y OR), ¿cuál es la forma más eficiente de extraer la fórmula booleana representada por el circuito? ¿Existe un algoritmo polytime para este problema? $C$ $n$

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

¿Qué tipo de puertas tiene el circuito?

Lev Reyzin

¿Qué restricciones en fan-in o fan-out? Si es solo un despliegue único, es trivial: el circuito en sí mismo es esencialmente un AST para la fórmula.

Mark Reitblatt

Fan-in limitado para ser general. Pero para ser precisos, digamos que AND y OR tienen fan-in 2. En muchas referencias en la literatura, encuentro que un circuito y fórmulas se usan indistintamente, pero quiero saber si convertir un circuito en una fórmula es fácil problema.

Nikhil

En general, se esperaría que cualquier fórmula equivalente pudiera tener un tamaño exponencial incluso para un circuito pequeño.

Kristoffer Arnsfelt Hansen

Las fórmulas de tamaño polinómico son equivalentes a los circuitos

. No se sabe que los circuitos de polisización (

) sean equivalentes a

. Las fórmulas y los circuitos se usan indistintamente cuando la profundidad del circuito está limitada.

N C^{1}

$NC^1$

P / p o l y

$P/poly$

N C^{1}

$NC^1$

Kaveh

Respuestas:

Si entiendo su pregunta correctamente, diría que podría usar la reducción estándar de CIRCUIT-SAT a SAT: represente cada puerta como una nueva variable, y luego represente todo el circuito en forma CNF, con cada cláusula que tiene la forma , donde es la nueva variable, y la fórmula para la puerta está dada por , usando las variables para otras puertas para representar las entradas. Esto puede hacerse mediante un recorrido simple (en tiempo lineal, que es claramente óptimo). $(v\leftrightarrow\phi)$ $v$ $\phi$

Por ejemplo, si tiene tres entradas, , y , con puertas AND que unen y , así como y , y una puerta OR que une sus salidas, puede introducir tres variables para representar las puertas ( , y , respectivamente) y reescribir la fórmula a $x_1$ $x_2$ $x_3$ $x_1$ $x_2$ $x_2$ $x_3$ $v_1$ $v_2$ $v_3$ Tenga en cuenta que la variable de salida se incluye explícitamente.

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

Introducción a los algoritmos por Cormen et al. explica esto en detalle, en el capítulo sobre NP-Completeness.

Magnus Lie Hetland
fuente

¿CIRCUIT-SAT no utiliza puertas de abanico 1?

Mark Reitblatt

Claro, pero hasta donde puedo ver, eso no afecta la reducción / transformación. La idea de representar cada salida como una nueva variable significa que puede reutilizar cada salida como entrada varias veces (correspondiente a un abanico arbitrariamente grande). En otras palabras, la solución dada en esta respuesta debería funcionar para circuitos arbitrarios.

Magnus Lie Hetland

Supongo que esto no es lo que se pide. Creo que lo que se quiere es hacer una fórmula en el mismo conjunto de variables que el circuito.

Kristoffer Arnsfelt Hansen

Hm. Sí, probablemente tengas razón. Introducir las nuevas variables tiene sentido en el caso de CIRCUIT-SAT a CNF-SAT, pero no en un entorno más general, estoy de acuerdo.

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