¿El problema de encontrar operadores para satisfacer una lista de variables booleanas NP está completo?

Esto es similar a SAT, excepto que conocemos la asignación de cada variable, pero no conocemos la asignación de ningún operador booleano. En ese caso, ¿encontrar la asignación de cada operador para que la expresión evalúe un valor booleano dado es un problema NPC?

En realidad, me preguntaba si encontrar asignación de operadores aritméticos para satisfacer una expresión aritmética entera (por ejemplo, $1$ $op_1$ $3$ $op_2$ $7$ $op_3$ $op_4$ = 10) ¿NP está completo?

Con la suma y la resta, creo que el problema de Partición , que es NP-hard, se reduce a su segundo problema.

Dado un conjunto creamos el problema$S = \{s_1, s_2, \ldots, s_n\}$

o p 1 s 2 o p 2 s 3 o p 3 … o p n - 1 s n = 0 . $s_1$ $op_1$ $s_2$ $op_2$ $s_3$ $op_3$ $\ldots op_{n-1}$ $s_n = 0$

Si existe una solución, creamos dos conjuntos:

$S_1 = \{s_1\}\cup \{s_i | op_{i-1} = +\}$

$S_2 = \{s_i | op_{i-1} = -\}$

Estos dos conjuntos tienen que tener la misma suma por la configuración de nuestro problema original, por lo que el problema de partición está resuelto. Esto muestra que no solo es difícil encontrar la solución real a este problema, de hecho es NP difícil determinar si existe una solución (al menos para sumar y restar).

Para un conjunto de operaciones que no permite la creación de enteros negativos, digamos multiplicación y suma, no está tan claro. Además, esto solo muestra que el problema es débilmente NP-duro; puede haber una reducción que dé un resultado más fuerte que esto.

Respuesta corta. La versión del operador de SAT se puede resolver de manera eficiente, al menos, si asumimos circuitos arbitrarios de puertas de dos entradas sin despliegue, sobre cualquier elección deseada de conjunto de puertas.

Respuesta larga. Asumo la siguiente forma del problema booleano:

$x \in \{0,1\}^n$G C G x x x $n \geqslant 2$$\mathcal G$$C$$\mathcal G$ $x$$x$$x$$C$

En particular, no imponemos una estructura particular en los circuitos (aparte de ser árboles binarios), no permitimos el despliegue (por lo que cada bit de se usa solo una vez), y las puertas pueden ser asimétricas. Al permitir solo compuertas de dos bits, excluyo la compuerta NOT (pero que puede simularse teniendo múltiples compuertas que están relacionadas entre sí por negaciones, como AND / NAND ; y también excluyo compuertas que simplemente generan constantes sin entradas , de modo que el número de compuertas en el circuito de hecho siempre será para una entrada de bits. En aras de la brevedad, me referiré a 2-TREE-OPSAT a continuación simplemente como OPSATx n - 1 $C$$x$$n-1$$n$; aunque el análisis del problema puede ser mucho más difícil para los circuitos que permiten puertas de entrada k arbitrarias ( k-TREE-OPSAT ) o que permiten el despliegue (que podríamos llamar k-FANOUT-OPSAT ).

[ Editado para agregar : podemos adaptar esto fácilmente para considerar el problema más general de la revisión actual de su pregunta, en la que intentamos asignar una dada a un valor objetivo , intercambiando los roles de y en el análisis a continuación; esto tiene el efecto de intercambiar los roles de AND y OR , NAND y NOR , etc. ] b ∈ { 0 , 1 } 0 $x \in \{0,1\}^\ast$$b \in \{0,1\}$$0$$1$$\def\et{\wedge}\def\ou{\vee}\def\AND{\mathop{\text{AND}}}\def\NAND{\mathop{\text{NAND}}}\def\OR{\mathop{\text{OR}}}\def\NOR{\mathop{\text{NOR}}}\def\EQUAL{\mathop{\text{EQUAL}}}\def\PARITY{\mathop{\text{PARITY}}}$

Para una elección fija de , el problema de elegir un árbol adecuado con puertas adecuadas no es diferente de una disyunción lógica: usar equivalencias como podemos realizar reducciones entre colecciones que relacionan conjuntos de compuertas más complicados con conjuntos de compuertas simples (y potentes); a puede hablar de que un conjunto de compuerta puede emular otras compuertas que no pertenecen al conjunto, eligiendo sabiamente algún elemento de que tenga el mismo efecto (cuando se presenta con una entrada particular) como una compuerta . En particular, ciertas combinaciones de compuertas (como ) pueden simular la función constante que produce$x \in \{0,1\}^n$

Procedemos considerando conjuntos de compuertas que incluyen diferentes tipos de compuertas , más tarde excluyendo esas compuertas de casos posteriores del análisis, para mostrar que los conjuntos de compuertas que involucran a cualquiera de las compuertas conducen a un problema tratable. Procederemos en el orden del número de cadenas de dos bits que satisfacen la puerta en cuestión, comenzando desde la puerta constante hasta la puerta constante .$G$$1$$0$

1. Para cualquier conjunto de compuerta que contenga la compuerta constante , simplemente podemos construir un circuito utilizando esa compuerta sola, en cuyo caso acepta cualquier .$\mathcal G$$G(x,y) = 1$$C$$C$$x$

2. O y NAND. Para cualquier conjunto de compuerta que contenga : si todas las demás compuertas satisfacen , entonces no hay ventaja en elegir otra compuerta pero en la construcción del circuito . Un circuito de solo puertas acepta cualquier cadena excepto . De lo contrario, existe una puerta tal que es tautóloga. Entonces, cualquier instancia de OPSAT con es fácil; y observaciones similares se aplican para .$\mathcal G$$\OR$$G \in \mathcal G$$G(x,y) \implies \OR(x,y)$$\OR$$C$$\OR$$x \in 0^\ast$$G \in \mathcal G$$\{G, \OR\}$$\OR \in \mathcal G$$\NAND \in \mathcal G$

3. Puertas de implicación. Considere la puerta , que solo genera cero si . Para lo que sigue, se aplicará un análisis similar para la puerta . Considere cualquier cadena . Si termina en , descomponga en subcadenas de la forma ; en cada uno de estos , aplicamos recursivamente de derecha a izquierda, lo que produce la salida para cada . (Para una subcadena de longitud 1, usamos el circuito trivial, es decir, dejamos esa entrada sola). De manera similar, si$G(x,y) = \neg x \ou y$$(x,y) = (1,0)$$G'(x,y) = x \ou \neg y$
   
   $x \in \{0,1\}^n$$x$$0$$x$$w_j = 1^\ast 0$$w_j$$G$$0$$w_j$$x$ termina en , descompone en subcadenas de la forma , y aplica recursivamente de izquierda a derecha en cada , lo que produce la salida para cada . Así, podemos reducir el problema a la construcción de circuitos que están satisfechos, ya sea por o , donde es el número de subseries o . Para , podemos aceptar ya sea usando puertas aplicando de forma recursiva de izquierda a derecha. Esto solo deja el caso$1$$x$$w_j =0^\ast 1$$G$$w_j$$1$$w_j$$0^m$$1^m$$m$$1^\ast0$$0^\ast 1$$m \geqslant 2$$G$$G$$m = 1$ , para el cual el caso problemático son entradas . Para , cualquier circuito que consista solo en compuertas solo producirá cadenas más cortas de la forma , en última instancia, arrojará la cadena de un solo bit : de modo que ningún circuito de compuertas pueda satisfacerse esta entrada Si también hay una puerta para la cual , entonces es tautóloga; o, si hay una puerta para la cual , podemos reducir las cadenas de la forma$x \in 1^\ast 0$
   
   $x= 1^\ast 0$$G$$1^\ast 0$$0$$G$$H \in \mathcal G$$H(1,0) = 1$$\{G,H\}$$H \in \mathcal G$$H(1,1) = 0$$11^\ast 0$a cadenas de la forma , aplicando a los primeros dos bits de . De lo contrario, no se puede construir un circuito que acepte . Por lo tanto, para cualquier gate-set que contenga una compuerta de implicación, OPSAT es fácil.$(1^\ast 0)^\ast$$H$$x$$x \in 1^\ast 0$
   
   $\mathcal G$

4. Negaciones de proyecciones. Considere las puertas y . Consideramos , el análisis con es similar. Por sí solo, puede aceptar cualquier cadena en para al reducir los bits finales a un solo bit y luego aplicar ; y puede aceptar de manera similar para reduciendo los bits finales a un solo bit y luego aplicando el circuito$\neg \pi_1(x,y) = \neg x$$\neg \pi_2(x,y) = \neg y$$\neg \pi_1$$\neg \pi_2$$\neg \pi_1$$0(0|1)^{n-1}$$n \geqslant 2$$n-1$$\neg \pi_1$$1(0|1)^{n-1}$$n \geqslant 3$$n-2$$\neg \pi_1(\neg \pi_1(x_1, x_2),x_3)$. Las únicas entradas que los circuitos no pueden aceptar son entonces u ; determinar si alguna puerta suplementaria los acepta es trivial. Por lo tanto, OPSAT es fácil para las negaciones de proyecciones.$\neg \pi_1$$10$$11$

5. PARIDAD E IGUALDAD . Considere la puerta . El conjunto de puertas obviamente solo puede satisfacerse con precisión mediante cadenas con un número impar de 1s; Consideramos el beneficio de agregar cualquier otra puerta.$\PARITY(x,y) = (x \ou \neg y) \et (\neg x \ou y)$$\mathcal G = \{\PARITY\}$$x \in \{0,1\}^n$

   • Cualquier conjunto de compuertas que contenga tanto como o puede simular circuitos que contienen compuertas o (respectivamente) para entradas fijas, que son casos fáciles de OPSAT .$\PARITY$$\AND$$\NOR(x,y) = \neg(x \ou y)$$\OR$$\NAND$
   • Se puede usar o para simular o en subcadenas de dos bits de paridad par, para que podamos reducir los conjuntos de puertas con estos puertas y al caso anterior.$\pi_1(x,y) = x$$\pi_2(x,y) = y$$\AND$$\NOR$$\PARITY$
   • $\PARITY$ junto con es tautólogo.$\EQUAL = \neg \PARITY$
   • Si complementamos con la puerta , podemos aceptar cualquier cadena de paridad par excepto aplicando a una subcadena de y luego aplica un circuito al resto. De manera similar, junto con puede aceptar cualquier cadena excepto las de la forma . Complementar con y nos permite construir circuitos que aceptan todas las entradas excepto y$\PARITY$$G_{01} = \neg x \et y$$x \in (11)^\ast 0^\ast$$G_{01}$$01$$x$$\PARITY$$\PARITY$$G_{10} = x \et \neg y$$x \in 0^\ast (11)^\ast$$\PARITY$$G_{01}$$G_{10}$$x \in 0^\ast$$x = 11$ .
   • Finalmente, si complementamos con la puerta constante , podemos aceptar cualquier entrada, excepto o aplicando una puerta a una subcadena o , que se reduce al caso de paridad impar.$\PARITY$$Z(x,y) = 0$$x \in (11)^\ast$$x \in 0^\ast$$G$$01$$10$

   Por lo tanto, OPSAT es fácil para cualquier contenga . Se aplica un análisis similar para la puerta como para la puerta : porque , circuitos Las puertas de cuentan esencialmente la paridad del número de s en la entrada. Entonces podemos reducir el análisis para al de intercambiando y .$\mathcal G$$\PARITY$
   
   $\EQUAL$$\PARITY$$\EQUAL(x,y) = \neg \PARITY(x,y) = \neg \PARITY(\neg x, \neg y)$$\EQUAL$$0$$\EQUAL$$\PARITY$$0$$1$

6. Puertas de proyección. Las puertas y , tomadas solas, solo pueden construir circuitos que acepten cadenas que comiencen o terminen en , respectivamente. Considere el efecto de aumentar la puerta con cualquier otra puerta (un análisis similar es válido para ):$\pi_1(x,y) = x$$\pi_2(x,y) = y$$1$$\pi_1$$\pi_2$

   • Permitir tanto como permite la construcción de un circuito de "selección", que simplemente emite cualquier bit desde la entrada; estos pueden aceptar cualquier , y complementarlos con cualquier puerta para la cual permite construir un circuito satisfecho para cualquier .$\pi_1$$\pi_2$$x \ne 0^n$$G$$G(0,0) = 1$$x$
   • Si complementamos con o , podemos simular o una puerta de tipo implicación para entradas fijas; OPSAT está resuelto para ambos casos.$\pi_1$$\NOR$$G_{01} = \neg x \et y$$\OR$
   • Si complementamos con , , la puerta constante , o cualquier combinación de ellas, no obtendremos poder de aceptación adicional, de modo que todavía solo puede aceptar cadenas que comiencen con .$\pi_1$$\AND$$G_{10} = x \et \neg y$$Z(x,y) = 0$$1$

   Por lo tanto, para cualquier otra puerta con la que podamos complementar (o ), obtenemos un conjunto , no obtenemos poder de aceptación adicional sobre solo (o ), o podemos reducirlo a un caso fácil anterior de OPSAT . Entonces, cualquier instancia de OPSAT con o es fácil.$\pi_1$$\pi_2$$\pi_1$$\pi_2$$\pi_1 \in \mathcal G$$\pi_2 \in \mathcal G$

7. Puertas con función Delta. Considere las compuertas de dos bits para las cuales solo hay una entrada que las satisface: , , , y . Los circuitos hechos solo con compuertas solo pueden aceptar la cadena : complementarlos con cualquier otra compuerta de función delta les permite simular , o , que son casos resueltos; observaciones similares se aplican a . Además, el conjunto de puertas se puede utilizar para simular también la$\AND$$\NOR$$G_{10}(x,y) = x \et \neg y$$G_{01}(x,y) = \neg x \et y$$\AND$$1^\ast$$\EQUAL$$\pi_1$$\pi_2$$\NOR$$\{G_{01}, G_{10}\}$$\PARITY$portón. Por lo tanto, podemos centrarnos en la puerta o , posiblemente complementada con la puerta . Nos centramos en , siendo el caso de similar. Los circuitos hechos de solo se pueden construir para aceptar , excepto para la cadena , aplicando un circuito arbitrario a los bits finales y luego aplicando el circuito . Claramente, la cadena no puede ser aceptada por o por ; y podemos demostrar por inducción que cualquier$G_{10}$$G_{01}$$Z(x,y) = 0$$G_{10}$$G_{01}$
   
   $G_{10}$$1(0|1)^{n-1}$$11$$n-2$$G_{10}(x_1, G_{10}(x_2, x_3))$$11$$G_{10}$$Z$$G_{10}$El circuito que acepta una cadena debe tener resultados intermedios de las compuertas en la rama más a la izquierda, todos con un , hasta la entrada más a la izquierda. No se obtienen beneficios adicionales al agregar puertasPor lo tanto, los circuitos solo pueden aceptar .$1$$Z$$G_{10}$$x \in 1(0|10|11)(0|1)^\ast$

8. Finalmente, los circuitos compuestos solo por puertas no aceptan entradas.$Z$

Como cada puerta da lugar a una clase de entradas bien definida y, en general bastante grandes que acepta, con puertas adicionales que tienden a trivializar el problema, nos encontramos con que 2-ÁRBOL-OPSAT está en P .