Está encontrando solução para um sistema de equações 2sat separadas por ou (formulário DNF) em NP

Question

Eu quero saber se encontrar solução para um número específico de equações de 2SAT Sepearted por ou portão (Formulário DNF como abaixo) está em P ou NP.

A equação tem variáveis N Total N e cada cláusula é uma equação de 2,sates em si em um subconjunto de variáveis de 1 a n. Exemplo:

f= [(x1 || x2) && (! x2 || x3) && (x3 || x4)] ||[(x2 || x5) && (x3 || x6) && (! x4 ||! x6)] ||....

A equação f é um DNF de equações 2sat, que dizem m cláusulas.Está encontrando uma solução para isso no NP?Se sim como?

Além disso, especificamente, eu também quero saber se encontrar instâncias falsas da equação F está em p ou NP também.

Answer 1

• primeiro, deixe-me observar que o título da pergunta é um pouco enganosa, porque $ P $ é um subconjunto de $ NP $ . Veja também o comentário do filme de Yuval. Eu suponho o que você pretendido para perguntar é se está em $ p $ ou em $ np \ setminus p $ .
• Além disso, o nome "DNF" refere-se especificamente a uma disjunção de conjunções elementar , não uma disjunção de funções arbitrárias. O que você está descrevendo não é um DNF, mas uma disjunção de CNFs.

Com isso fora do caminho, aqui está a minha resposta.

---

.

.

1. Para satisfazer uma disjunção de 2-CNFs, tudo que você precisa é satisfazer um deles. Então, se você aplicar o algoritmo 2-SAT para o primeiro dos CNFs e obter um "Sim", a resposta para todo o problema é "sim". Caso contrário, você acabou de passar para o segundo, e assim por diante. Não deveria demorar muito, já que você só tem m deles. Se nenhum deles puder ser satisfeito individualmente, ou seja, todos eles são zeros constantes, então, obviamente, a coisa toda é um zero constante.

   Portanto, a resposta à primeira parte é: O problema está em p, com o seguinte algoritmo de decisão:

   Para cada 2-CNF, aplique o algoritmo "normal" 2-SAT (a regra de resolução) para determinar se é satisfatório ou não. Se "sim", basta retornar "sim". Se você passou por todos eles sem encontrar um "sim", então retorne "não".

---

.

2. Agora, encontrar os casos "falsos" dessa fórmula (também conhecido como o problema da tautologia) é outra questão inteiramente. Por um lado, a tautologia para ORS de AND OS ORS é equivalente à satisfação de es de ORS de AND, pela regra de de Morgan. Mas isso é apenas um caso mais geral de um problema já geral SAT, não é?

   Considere o que acontece quando você restringe o conjunto de possíveis fórmulas àquelas em que cada disjunção de dois elementos é realmente apenas um elemento, repetido. Então é uma fórmula como $$ F= [(x_1 \ vee x_1) \ & (\ NEG X_2 \ Vee \ NEG X_2) \ & (x_3 \ Vee x_3)] \ Vee [(x_2 \ vee x_2) \ & (x_4 \ vee x_4) \ & ( x_5 \ vee x_5)] \ Vee ... $$ que é equivalente a $$ F= [x_1 \ & \ neg x_2 \ & x_3] \ vee [x_2 \ & x_4 \ & x_5] \ Vee ... $$ Qual é apenas um DNF normal. Após a transformação de Morgan, você recebe um CNF normal, cuja satisfação é conhecida por ser NP-Hard. Portanto, qualquer problema que inclua este como um subconjunto também será pelo menos np-hard.

   Obviamente, o problema em questão não será fora np, porque ainda é polinomomialmente verificável. Então a resposta à sua segunda pergunta é "no NP, mas não em P".