Verificando soluções exclusivas do SAT

Considere o seguinte problema: dada uma fórmula CNF e uma atribuição que satisfaça essa fórmula, existe outra atribuição satisfatória para essa fórmula?

Qual é a complexidade desse problema? (Certamente está em NP, mas também é difícil em NP?)

E se você não receber a tarefa e apenas quiser decidir se a fórmula tem uma tarefa satisfatória exclusiva?

Obrigado.

O problema de decidir se uma determinada fórmula CNF tem uma atribuição satisfatória diferente de uma dada é facilmente demonstrado como completo NP, transformando uma fórmula CNF para adicionar uma solução trivial. Esse problema é chamado de "Outro Problema de Solução (ASP) da SAT" em [YS03], onde é usado para fornecer uma prova sistemática de que (as versões de decisão) dos ASPs de muitos outros problemas também são NP-completos.

O problema de decidir se uma determinada fórmula da CNF tem uma atribuição única satisfatória ou não (portanto, você deve responder "não" se a fórmula não tiver nenhuma tarefa satisfatória ou mais de uma tarefa satisfatória) está completo nos EUA . EUA contém os dois UP e coNP .

Referências

[YS03] Takayuki Yato e Takahiro Seta. Complexidade e integridade de encontrar outra solução e sua aplicação em quebra-cabeças. Transações do IEICE sobre fundamentos de eletrônica, comunicações e ciências da computação, E86-A (5): 1052-1060, maio de 2003.

Editar : Uma versão anterior (revisão 1) desta resposta continha uma confusão entre a versão da decisão e a versão da pesquisa. Foi consertado.

Lembro-me de Yoram Moses e eu estudando esse problema em meados da década de 1980 (à luz de algumas aplicações) e descobrindo que, para muitos problemas naturais de NPC, o problema de encontrar uma segunda solução alternativa (ou decidir se existe) é NPC. Descobrimos então que isso era conhecido, mas não me lembro do juiz, e não conseguimos encontrar um (isto é, um anterior a meados da década de 1980) agora. Mas tenho certeza de que me lembro corretamente do acima.

Apenas um comentário para Ryan. O fato de um teorema poder ser dado como exercício nas aulas atuais não o torna menos atraente. Deveria ter sido publicado em um artigo com um título adequado no momento em que foi descoberto ...

Oded Goldreich

Aqui, escrevo um trecho do seguinte artigo:

Valiant, LG e Vazirani, VV 1986. NP é tão fácil quanto detectar soluções exclusivas. Theor. Comput. Sci. 47, 1 (novembro de 1986), 85-93. DOI = http://dx.doi.org/10.1016/0304-3975(86)90135-0

Para cada problema conhecido de NP-completo, o número de soluções de suas instâncias varia em uma ampla faixa, de zero a exponencialmente. Portanto, é natural perguntar se a intratabilidade inerente ao problema de NP completo é causada por essa ampla variação. Damos uma resposta negativa a essa pergunta usando a noção de redutibilidade aleatória do tempo polinomial. Mostramos que os problemas de distinguir entre instâncias do SAT com zero ou uma solução, ou de encontrar soluções para instâncias do SAT com uma solução única, são tão difíceis quanto o SAT, sob reduções aleatórias.

Sugiro também olhar para o artigo relevante:

Beigel, R., Buhrman, H. e Fortnow, L. 1998. NP pode não ser tão fácil quanto detectar soluções únicas. Em Anais do Trigésimo Simpósio Anual da ACM sobre teoria da computação (Dallas, Texas, Estados Unidos, 24 a 26 de maio de 1998). STOC '98. ACM, Nova Iorque, NY, 203-208. DOI = http://doi.acm.org/10.1145/276698.276737

$DP=\{(L_1 ∩ L_2)| L_1 \in NP, L_2\in CoNP\}$

Andreas Blass e Yuri Gurevich, Sobre o problema único de satisfação,

A solução para ambos os problemas, UNIQUE SAT e OUTRO SAT, com uma classificação completa de complexidade, pode ser encontrada no artigo

L. Juban: Teorema da dicotomia para o problema de satisfação única generalizada http://link.springer.com/chapter/10.1007%2F3-540-48321-7_27