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

11

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 op1 3 op2 7 op3 op4 = 10) NP está completo?

DSounders
fonte
2
Portanto, se entendi corretamente, você sabe que a fórmula é satisfatória e deseja conhecer uma atribuição dos operadores booleanos. Apenas atribuir o operador a todas as "variáveis de operação" e está feito. Não sei sobre o segundo problema, mas parece interessante.
George
3
@ GeorgeB: Não acho que a solução esteja correta. E se todos os valores booleanos estiverem definidos como false? Esta pergunta é interessante, mas pode precisar de um pouco de trabalho. De que conjunto de operadores booleanos estamos escolhendo? Presumivelmente, você quer dizer um subconjunto interessante de operadores booleanos binários como {,,} . Se você incluir todos os operadores booleanos binários, o problema é trivial - basta escolher o mapa constante como 'true'.
Huck Bennett
1
Como Huck disse, escolha para todos os i . No entanto, se você restringir os operadores a um conjunto específico, a pergunta será mais interessante. Da mesma forma para o caso aritmético. xopiy=1i
Kaveh
parece que ele pode ter alguma conexão com QBFs ou possivelmente reduzido a ele. provavelmente um QBF pode ser construído que, quando resolvido, fornece aos operadores. certo? em inspeção rápida, parece que o Pspace está completo ... também é preciso definir a precedência se não houver parênteses. E maior que OU? o problema parece mais natural, talvez quando parênteses / agrupamentos podem ser definidos.
vzn
@GeorgeB. Me desculpe, eu não deixei claro. A avaliação de uma expressão booleana pode ser qualquer dado valor booleano, 0 ou 1.
DSounders

Respostas:

10

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 3o p n - 1 s n = 0 . s1 op1 s2 op2 s3 op3 opn1 sn=0

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

S1={s1}{si|opi1=+}

S2={si|opi1=}

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.

SamM
fonte
1
Eu acho que a prova pode ser adaptado para o caso com bastante facilidade, basta definir o problema alvo s 1 ... s n = 1 . Então uma solução implica que o denominador é o mesmo que o numerador (assumindo s i > 0 para todo i ). É claro que isso não é o caso dos quatro operadores, mas também teríamos que lidar com a ordem das operações. ×/÷s1sn=1si>0i
Luke Mathieson
Obrigado, @ Sam e Luke. E se misturarmos todos os quatro operadores? Intuitivamente, ter mais operadores só tornará o problema mais complexo, mas não vejo uma prova direta.
DSounders
Ainda pensando nos quatro. Também podemos obter facilmente, mas ainda são apenas dois de cada vez. +/÷
Luke Mathieson
1
Além disso, uma referência para a completude (forte) PARTIÇÃO DO PRODUTO: "" Partição do produto "e problemas relacionados à confiabilidade do agendamento e dos sistemas: complexidade e aproximação computacional" sciencedirect.com/science/article/pii/S0377221710003905NP
Luke Mathieson
4

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{0,1}nG C G x x x Cn2GCG xxxC

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 nCxn1n; 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}01

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

OR(x,y)(AND(x,y)PARITY(x,y))
GGG{OR,NAND}1: dizemos que esses conjuntos de portas são tautológicos .

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 .G10

  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 .GG(x,y)=1CCx

  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 .GORGGG(x,y)OR(x,y)ORCORx0GG{G,OR}ORGNANDG

  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, seG(x,y)=¬xy(x,y)=(1,0)G(x,y)=x¬y

    x{0,1}nx0xwj=10wjG0wjx 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 caso1xwj=01Gwj1wj0m1mm1001m2GGm=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 formatox10

    x=10G100GHGH(1,0)=1{G,H}HGH(1,1)=0110para 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.(10)Hxx10

    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¬π1(x,y)=¬x¬π2(x,y)=¬y¬π1¬π2¬π10(0|1)n1n2n1¬π11(0|1)n1n3n2¬π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.¬π11011

  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¬y)(¬xy)G={PARITY}x{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 .PARITYANDNOR(x,y)=¬(xy)ORNAND
    • 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.π1(x,y)=xπ2(x,y)=yANDNORPARITY
    • PARITY junto com é tautológico.EQUAL=¬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 ePARITYG01=¬xyx(11)0G0101xPARITYPARITYG10=x¬yx0(11)PARITYG01G10x0x=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.PARITYZ(x,y)=0x(11)x0G0110

    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 .GPARITY

    EQUALPARITYEQUAL(x,y)=¬PARITY(x,y)=¬PARITY(¬x,¬y)EQUAL0EQUALPARITY01

  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 ):π1(x,y)=xπ2(x,y)=y1π1π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 .π1π2x0nGG(0,0)=1x
    • Se suplementarmos com ou , poderemos simular ou uma porta do tipo implicação para entradas fixas; OPSAT é resolvido para ambos os casos.π1NORG01=¬xyOR
    • 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 .π1ANDG10=x¬yZ(x,y)=01

    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π1Gπ2G

  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 oANDNORG10(x,y)=x¬yG01(x,y)=¬xyAND1EQUALπ1π2NOR{G01,G10}PARITYportã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 qualquerG10G01Z(x,y)=0G10G01

    G101(0|1)n111n2G10(x1,G10(x2,x3))11G10ZG10O 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 .1ZG10x1(0|10|11)(0|1)

  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 .

Niel de Beaudrap
fonte
1
@DSounders: com relação à sua revisão recente do problema para determinar se existe um circuito que mapeia para algum valor-alvo , em vez de apenas o caso especial , o mesmo análise como na minha resposta atual ainda é suficiente para mostrar que o problema está em P ; apenas os papéis dos portões mudam. Por exemplo, ao trocar os resultados desejados e , trocamos efetivamente os papéis de AND e OR , NAND e NOR , os portões semelhantes a implicações com as outras funções delta, etc.Cx b{0,1}b=101
Niel de Beaudrap