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, = 10) NP está completo?
cc.complexity-theory
np-hardness
DSounders
fonte
fonte
Respostas:
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 problemaS={s1,s2,…,sn}
o p 1 s 2 o p 2 s 3 o p 3 … o p n - 1 s n = 0 .s1 op1 s2 op2 s3 op3 …opn−1 sn=0
Se existir uma solução, criamos dois conjuntos:
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.
fonte
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:
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 nC 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 1x∈{0,1}∗ b∈{0,1} 0 1
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 produzindox∈{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
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 .G G(x,y)=1 C C x
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 .G OR G∈G G(x,y)⟹OR(x,y) OR C OR x∈0∗ G∈G {G,OR} OR∈G NAND∈G
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, seG(x,y)=¬x∨y (x,y)=(1,0) G′(x,y)=x∨¬y
x∈{0,1}n x 0 x wj=1∗0 wj G 0 wj 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 caso1 x wj=0∗1 G wj 1 wj 0m 1m m 1∗0 0∗1 m⩾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 formatox∈1∗0
x=1∗0 G 1∗0 0 G H∈G H(1,0)=1 {G,H} H∈G H(1,1)=0 11∗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∗0)∗ H x x∈1∗0
G
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¬π1(x,y)=¬x ¬π2(x,y)=¬y ¬π1 ¬π2 ¬π1 0(0|1)n−1 n⩾2 n−1 ¬π1 1(0|1)n−1 n⩾3 n−2 ¬π1(¬π1(x1,x2),x3) . 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.¬π1 10 11
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∨¬y)∧(¬x∨y) G={PARITY} x∈{0,1}n
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 .G PARITY
EQUAL PARITY EQUAL(x,y)=¬PARITY(x,y)=¬PARITY(¬x,¬y) EQUAL 0 EQUAL PARITY 0 1
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 ):π1(x,y)=x π2(x,y)=y 1 π1 π2
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.π1 π2 π1 π2 π1∈G π2∈G
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 oAND NOR G10(x,y)=x∧¬y G01(x,y)=¬x∧y AND 1∗ EQUAL π1 π2 NOR {G01,G10} 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 qualquerG10 G01 Z(x,y)=0 G10 G01
G10 1(0|1)n−1 11 n−2 G10(x1,G10(x2,x3)) 11 G10 Z G10 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 G10 x∈1(0|10|11)(0|1)∗
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 .
fonte