Reduzindo #SAT para # MONOTONE-2SAT

8

O problema # MONOTONE-2SAT é conhecido por # P-complete. Isso significa que #SAT pode ser reduzido a ele. Minha pergunta é: dada uma instância #SAT , que é a transformação que converte F na instância correspondente # MONOTONE-2SAT F ′ ?FFF′

A segunda questão é: deixar ser o número de soluções de F ' , e deixá- K ser um número de soluções de F . Does K ' = K ? Ou devemos usar uma transformação reversa que converta K ′ em K ?K′F′KFK′=KK′K

cc.complexity-theory ds.algorithms complexity-classes sat Giorgio Camerani
fonte
Você poderia motivar por que votou contra esta pergunta?
Giorgio Camerani
Não sou eu quem votou na questão, mas não ficarei surpreso se alguém considerar que a questão é muito básica.
Tsuyoshi Ito
Acho que não. Não é mais básico do que algumas outras questões levantadas neste site. De qualquer forma, uma pergunta, mesmo que básica, pode ser útil. Minhas perguntas sobre limites inferiores nos clusters de soluções #SAT e SAT também podem ser consideradas muito básicas, mas não foram rejeitadas.
Giorgio Camerani
A primeira pergunta é bastante básica: essencialmente você perguntou o que era uma redução. A segunda pergunta também me prendeu uma vez, mas é resolvida pensando da maneira certa. O ponto principal da minha resposta é que a pergunta é fácil . Se você ainda acha que a pergunta está no nível certo depois de ler minha resposta, provavelmente minha resposta está mal escrita.
Tsuyoshi Ito
1
Walter, Tsuyoshi, embora essa discussão seja útil, um lugar melhor para ela é em meta.cstheory.stackexchange.com. Por que você não discute isso lá e adiciona um link para essa discussão aqui. FWIW, acho que a pergunta é relativamente inofensiva, mas um pouco mais de "por que estou perguntando" teria sido útil.
Suresh Venkat

Respostas:

7

Quanto à primeira pergunta, é isso que uma redução faz. Para saber como reduzir # 3SAT a # Monotone-2SAT, consulte a prova de # P-completude de # Monotone-2SAT [Val79b], que é baseada na # P-completude de Permanent [Val79a]. Para reduzir #SAT para # 3SAT, a redução de Cook de qualquer problema no NP para 3SAT é parcimoniosa e, portanto, reduz #SAT para # 3SAT.

A resposta para a segunda pergunta é não. A redução de [Val79a] de # 3SAT para permanente não preserva o número de soluções. Além disso, se fosse conhecida uma redução de #SAT para # Monotone-2SAT (ou Permanente) que preserva o número de soluções, a mesma redução reduziria a versão de decisão do SAT à versão de decisão do Monotone-2SAT (ou Correspondência bipartida), implicando P = NP.

Referências

Leslie G. Valiant. A complexidade de calcular o permanente. Teoria da Computação , 8 (2): 189–201, 1979. http://dx.doi.org/10.1016/0304-3975(79)90044-6

Leslie G. Valiant. A complexidade dos problemas de enumeração e confiabilidade. SIAM Journal on Computing , 8 (3): 410–421, agosto de 1979. http://dx.doi.org/10.1137/0208032

Tsuyoshi Ito
fonte
Obrigado por seus ponteiros para [Val79b] e [Val79a]. No que diz respeito à segunda resposta, não consigo entender: se um problema for # P-complete, ele poderá ser usado para resolver qualquer outro problema em #P. Agora, suponha que eu queira resolver #SAT: quero saber o número K de soluções de uma dada fórmula F; para fazer isso, reduzo F para uma instância F 'de # MONOTONE-2SAT e obtenho o número K' de soluções para F '. Agora, se conhecer K 'não me ajuda a conhecer K (ou seja, resolver # MONOTONE-2SAT não me ajuda a resolver #SAT) como pode # MONOTONE-2SAT ser # P-completo? Por que devo fazer tudo isso se não resolver o #SAT?
Giorgio Camerani 13/09/10
Deixe-me expressar um comentário lateral. É possível que eu tenha que pagar 40 dólares para ler um artigo com 31 anos? Acho isso absurdo e contra o espírito da ciência. Concordo que o artigo tenha entre 10 e 15 anos, pois pode ser considerado uma descoberta "patenteada". Mas pagar por um artigo de 31 anos é uma vergonha IMHO. Alguém poderia me indicar uma versão gratuita dele?
Giorgio Camerani
1
Quanto à segunda resposta, é possível calcular K a partir de K ′ (e F); caso contrário, um mapeamento de F para F 'não seria uma redução. No entanto, sua pergunta é se é possível fazer uma redução tal que K = K ′. A resposta é que não é possível.
Tsuyoshi Ito
@ Tsuyoshi Ito: Mais um comentário sobre sua segunda resposta. Ter o mesmo número de soluções não implica ter o mesmo espaço de solução. Uma instância A pode ter o mesmo número de soluções de uma instância B, mas as soluções de B podem ser distribuídas de uma maneira completamente diferente no espaço da solução.
Giorgio Camerani
1
Não conheço cópias disponíveis gratuitamente dos papéis que citei. Uma prova da # P-completude do Permanent está em muitos livros didáticos sobre complexidade computacional, que podem estar disponíveis em bibliotecas: por exemplo, Complexidade Computacional por Papadimitriou, Complexidade Computacional: Uma Perspectiva Conceitual por Goldreich e Complexidade Computacional: Uma Abordagem Moderna por Arora e Barak conter uma prova. (more)
Tsuyoshi Ito