Complexidade do problema (SAT para 3-SAT)?

7

É sabido que qualquer fórmula CNF pode ser transformada em tempo polinomial em uma fórmula 3-CNF usando novas variáveis ​​( veja aqui ). Se o uso de novas variáveis ​​não for permitido, isso nem sempre é possível (por exemplo, a fórmula da cláusula única:(x1 1∨x2∨x3∨x4))

Vamos definir o problema (SAT para 3-SAT): Dado F, uma fórmula CNF. É possível transformarFnum 3-CNF equivalente definido nas mesmas variáveis queF? - onde "equivalente" significa com o mesmo conjunto de modelos.

Qual é a complexidade desse problema?

Edit : Foi demonstrado na história que o problema é co-NP difícil.

complexity-theory satisfiability decision-problem complexity-classes Xavier Labouze
fonte
5
Nem sempre é possível transformar F, uma fórmula geral de CNF definida em n variáveis, em uma fórmula 3-CNF definida na mesma n variáveis ​​como F.
Xavier Labouze
4
Basta escolher uma fórmula de cláusula única F=x1 1∨x2∨x3∨x4
Vor
É possível depois de resolver o sat. Então você pode construir qualquer k-sat sem adicionar novas variáveis. Portanto, a complexidade deste problema é a complexidade de resolver sat.
Ilya Gazman
@Babibu - Você pode elaborar? (Acabei de editar a pergunta para vinculá-la à resposta da teoria que mostra que o problema é co-np difícil e preciso que "equivalente" signifique com o mesmo conjunto de modelos).
Xavier Labouze
O que você quer dizer com transformar ? Penso que há um limite superior PSPACE se o problema consiste em verificar a existência de uma fórmula 3CNF equivalente (com o mesmo conjunto de modelos) para uma dada fórmula em CNF
Pablo Munoz

Respostas:

3

Isso foi respondido no site do CS Theory StackExchange: https://cstheory.stackexchange.com/a/19833/5038

(Estou postando uma resposta aqui, para que esta pergunta não seja tratada como uma pergunta sem resposta e seja periodicamente rotacionada de volta para a página inicial pelo usuário da comunidade. Normalmente, as perguntas sem resposta positiva ou votada são re - exibido na primeira página de vez em quando.Como esta pergunta foi resolvida agora em outro lugar, não parece haver necessidade disso, desde que alguém vote ou aceite essa resposta, isso deve impedir que essa pergunta seja revertida para outra Marque a caixa do wiki da comunidade para não obter nenhum representante desta resposta.)

D.W.
fonte
Obrigado pela sua preocupação: +1
Xavier Labouze 27/12