O problema de encontrar operadores para satisfazer uma lista de variáveis ​​booleanas NP está completo?

Isso é semelhante ao SAT, exceto que conhecemos a atribuição de cada variável, mas não sabemos a atribuição de nenhum operador booleano. Nesse caso, encontrar a atribuição de cada operador para que a expressão avalie um determinado valor booleano é um problema do NPC?

Na verdade, eu estava pensando se encontrar a atribuição de operadores aritméticos para satisfazer uma expressão aritmética inteira (por exemplo, $1$ $op_1$ $3$ $op_2$ $7$ $op_3$ $op_4$ = 10) NP está completo?

Com adição e subtração, acho que o problema da Partição , que é difícil de NP, se reduz ao seu segundo problema.

Dado um conjunto , criamos o 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$

Se existir uma solução, criamos dois conjuntos:

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

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

Esses dois conjuntos precisam ter a mesma soma pela configuração do nosso problema original, para que o problema da partição seja resolvido. Isso mostra que não apenas é difícil encontrar a solução real para esse problema, mas também é difícil determinar se existe uma solução (pelo menos para adição e subtração).

Para um conjunto de operações que não permite a criação de números inteiros negativos, como multiplicação e adição, não é tão claro. Além disso, isso mostra apenas que o problema é fracamente NP-difícil; pode haver uma redução que dê um resultado mais forte que isso.

Resposta curta. A versão do operador do SAT é eficientemente solucionável - pelo menos, se assumirmos circuitos arbitrários de portas de duas entradas sem saída de ventilador, sobre qualquer escolha desejada de conjunto de portas.

Resposta longa. Eu assumo a seguinte forma do 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$

Em particular, não impomos nenhuma estrutura específica aos circuitos (além de serem árvores binárias), não permitimos a expansão (de modo que cada bit de seja usado apenas uma vez), e os portões podem ser assimétricos. Ao permitir apenas portas de dois bits, excluo a porta NOT (mas que pode ser simulada por ter várias portas relacionadas entre si por negações, como AND / NAND ; e também excluo portas que simplesmente emitem constantes sem entradas. , para que o número de portas no circuito seja sempre para uma entrada de bits. Por uma questão de brevidade, vou me referir a 2-TREE-OPSAT abaixo simplesmente como OPSATx n - 1 $C$$x$$n-1$$n$; embora a análise do problema possa se tornar muito mais difícil para circuitos que permitem portas de entrada k arbitrárias ( k-TREE-OPSAT ) ou permitem a saída de ventilador (que poderíamos chamar de k-FANOUT-OPSAT ).

[ Editado para adicionar : podemos facilmente adaptar isso para considerar o problema mais geral da revisão atual de sua pergunta, na qual tentamos mapear um determinado para um valor-alvo , trocando as funções de e na análise abaixo; isso tem o efeito de trocar os papéis de AND e OR , NAND e 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 uma escolha fixa de , o problema de escolher uma árvore adequada com portas adequadas não é diferente de uma disjunção lógica: usando equivalências como podemos realizar reduções entre coleções que relacionam conjuntos de portas mais complicados a conjuntos de portas simples (e poderosos); a pode falar de um conjunto de portas capaz de emular outras portas que não pertencem ao conjunto, escolhendo sabiamente algum elemento de que tenha o mesmo efeito (quando apresentado com uma entrada específica) que uma porta . Em particular, certas combinações de portas (como ) podem simular a função constante produzindo$x \in \{0,1\}^n$

Continuamos considerando os conjuntos de portas , incluindo diferentes tipos de portas , excluindo posteriormente as portas de casos posteriores da análise, para mostrar que os conjuntos de portas que envolvem qualquer um dos portões levam a um problema tratável. Prosseguiremos na ordem do número de strings de dois bits que satisfazem o gate em questão, iniciando do gate constante ao gate constante .$G$$1$$0$

1. Para qualquer conjunto de portas que contém a porta constante , podemos simplesmente construir um circuito usando apenas essa porta, caso em que aceita qualquer .$\mathcal G$$G(x,y) = 1$$C$$C$$x$

2. OR e NAND. Para qualquer conjunto de que contenha : se todos os outros portões satisfizerem , não há vantagem em escolher qualquer outro portão, exceto na construção do circuito . Um circuito de apenas gates aceita qualquer string, exceto . Caso contrário, existe um portão tal que é tautológico. Portanto, qualquer instância do OPSAT com é fácil; e observações semelhantes solicitar .$\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. Portões parecidos com implicações. Considere o portão , que emite apenas zero se . A seguir, uma análise semelhante será aplicada ao portão . Considere qualquer string . Se terminar em , decomponha em substrings da forma ; em cada um desses , aplicamos recursivamente da direita para a esquerda, o que gera a saída para cada . (Para uma substring de comprimento 1, usamos o circuito trivial, ou seja, deixe essa entrada em paz.) Da mesma forma, se$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 em , decompõe em substrings da forma e aplica recursivamente da esquerda para a direita em cada , o que gera a saída para cada . Assim, podemos reduzir o problema à construção de circuitos satisfeitos por ou , onde é o número de substrings ou . Para , podemos aceitar ou usando portões aplicando recursivamente da esquerda para a direita. Isso apenas deixa o 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 o qual o caso problemático são entradas . Para , qualquer circuito que consiste apenas de portas produzirá apenas cadeias mais curtas da forma , resultando finalmente na cadeia de bit único : de modo que nenhum circuito de portas possa ser satisfeito por esta entrada. Se também houver um portão para o qual , então é tautológico; ou, se houver um portão para o qual , podemos reduzir as strings do formato$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$para cadeias de caracteres da forma , aplicando aos dois primeiros bits de . Caso contrário, não pode ser construído nenhum circuito que aceite . Assim, para qualquer conjunto de portas que contenha uma porta do tipo implicação, o OPSAT é fácil.$(1^\ast 0)^\ast$$H$$x$$x \in 1^\ast 0$
   
   $\mathcal G$

4. Negações de projeções. Considere os portões e . Consideramos , sendo a análise com semelhante. Por si só, pode aceitar qualquer sequência em para , reduzindo os bits finais em um único bit e aplicando ; e também pode aceitar para reduzindo os bits finais em um único bit e aplicando o 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)$. As únicas entradas que os circuitos não podem aceitar são ou ; determinar se algum portão suplementar aceita isso é trivial. Assim, o OPSAT é fácil para as negações das projeções.$\neg \pi_1$$10$$11$

5. PARIDADE E IGUALDADE . Considere o portão . O conjunto de portas obviamente só pode ser satisfeito precisamente pelas cadeias com um número ímpar de 1s; consideramos o benefício de adicionar qualquer outro portão.$\PARITY(x,y) = (x \ou \neg y) \et (\neg x \ou y)$$\mathcal G = \{\PARITY\}$$x \in \{0,1\}^n$

   • Qualquer conjunto de portas que contenha e ou pode simular circuitos que contêm portas ou (respectivamente) para entradas fixas, que são casos fáceis de OPSAT .$\PARITY$$\AND$$\NOR(x,y) = \neg(x \ou y)$$\OR$$\NAND$
   • Ou ou pode ser usado para simular qualquer ou em subsequências de paridade par de dois-bits, de modo que pode reduzir porta-conjuntos com estes portões e no caso anterior.$\pi_1(x,y) = x$$\pi_2(x,y) = y$$\AND$$\NOR$$\PARITY$
   • $\PARITY$ junto com é tautológico.$\EQUAL = \neg \PARITY$
   • Se suplementarmos com a porta , podemos aceitar qualquer sequência de paridade par, exceto aplicando a um -substring de e, em seguida, aplicando um circuito ao restante. Da mesma forma, juntamente com pode aceitar qualquer string, exceto aquelas com o formato . Suplementar com e nos permite construir circuitos que aceitam todas as entradas, exceto e$\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, se suplementarmos com a porta constante , poderemos aceitar qualquer entrada, exceto ou aplicando uma porta para uma substring ou , reduzindo para o caso de paridade ímpar.$\PARITY$$Z(x,y) = 0$$x \in (11)^\ast$$x \in 0^\ast$$G$$01$$10$

   Assim, o OPSAT é fácil para qualquer contenha . Uma análise semelhante se aplica ao portão portão : porque , circuitos de portões contam essencialmente a paridade do número de s na entrada. Podemos então reduzir a análise de à de trocando e .$\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. Portões de projeção. Os portões e , tomado por conta própria, só pode construir circuitos que aceitam cordas inicial ou final em , respectivamente. Considere o efeito de aumentar o portão com qualquer outro portão (uma análise semelhante vale para ):$\pi_1(x,y) = x$$\pi_2(x,y) = y$$1$$\pi_1$$\pi_2$

   • Permitir e permite a construção de um circuito de "seleção", que simplesmente gera um bit único da entrada; eles podem aceitar qualquer e complementá-los com qualquer porta para a qual permite que um circuito satisfeito seja construído para qualquer .$\pi_1$$\pi_2$$x \ne 0^n$$G$$G(0,0) = 1$$x$
   • Se suplementarmos com ou , poderemos simular ou uma porta do tipo implicação para entradas fixas; OPSAT é resolvido para ambos os casos.$\pi_1$$\NOR$$G_{01} = \neg x \et y$$\OR$
   • Se suplementarmos com , , a porta constante ou qualquer combinação deles, não obteremos poder de aceitação adicional, de modo que ainda só pode aceitar cadeias começando com .$\pi_1$$\AND$$G_{10} = x \et \neg y$$Z(x,y) = 0$$1$

   Assim, para qualquer outro portão com o qual possamos suplementar (ou ), obtemos um conjunto tautológico, não obtemos poder de aceitação adicional sobre apenas (ou ) ou reduzir para um caso fácil anterior do OPSAT . Qualquer instância do OPSAT com ou é fácil.$\pi_1$$\pi_2$$\pi_1$$\pi_2$$\pi_1 \in \mathcal G$$\pi_2 \in \mathcal G$

7. Portões de função Delta. Considere os portões de dois bits para os quais existe apenas uma entrada que os satisfaça: , , e . Os circuitos feitos apenas com portas só podem aceitar a cadeia : complementá-los com qualquer outra porta de função delta permite simular , ou , que são casos resolvidos; observações semelhantes se aplicam a . Além disso, o conjunto de portas pode ser usado para simular o$\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ão. Assim, podemos nos concentrar no portão ou , possivelmente complementado com o portão . Focamos em , com o caso de sendo semelhante. Circuitos feitos apenas de podem ser construídos para aceitar , exceto a cadeia , aplicando um circuito arbitrário aos bits finais e, em seguida, aplicando o circuito . Claramente, a cadeia não pode ser aceita por ou por ; e podemos mostrar por indução que qualquer$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}$O circuito que aceita uma corda deve ter resultados intermediários dos portões no ramo mais à esquerda, todos com , até a entrada mais à esquerda. Nenhum benefício adicional é obtido com a adição de portasPortanto, os circuitos só podem aceitar .$1$$Z$$G_{10}$$x \in 1(0|10|11)(0|1)^\ast$

8. Finalmente, circuitos compostos apenas de portas não aceitam entradas.$Z$

À medida que cada porta dá origem a uma classe bem definida e geralmente bastante grandes de entradas que aceita, com portas adicionais tendem a trivialize o problema, descobrimos que 2-ÁRVORE-OPSAT é em P .