Complexidade de decidir se uma fórmula tem exatamente 1 tarefa satisfatória

11

O problema de decisão

Dada uma fórmula booleana , tem exatamente uma tarefa satisfatória?ϕϕϕ

pode ser visto em , -hard e -hard. Existe algo mais conhecido sobre sua complexidade?U P c o N PΔ2UPcoNP

sdcvvc
fonte

Respostas:

11

Seu problema é conhecido como que é completo. O problema está em mas não se sabe que é em reduções de tempo polinomiais determinísticas, em que a classe .L S D p D P D P = { L 1¯ L 2 | G 1 , G 2N P }UNIQUE-SATUSDpDpDp={L1L2¯L1,L2NP}

Papadimitriou e Yannakis [1] demonstraram que o conjunto de fórmulas exclusivamente satisfatórias está contido em . Isto segue a definição de : seja SAT e seja o conjunto de fórmulas com ou mais atribuições satisfatórias. Em relação à dureza de de , Blass e Gurevich [2] deram uma resposta parcial. Por um lado, eles mostraram que uma técnica de prova não relativizante seria necessária para resolver a questão. Entretanto, Valiant e Vazirani [3] reduziram aleatoriamente o tempo polinomial de mostrando dureza deD p L 1 L 2 2 D p UNIQUE-SATSAT D p UNIQUE-SATDpDpL1L22DpUNIQUE-SATSATDpUNIQUE-SAT sob reduções de tempo polinomiais aleatórias.

Quando se sabe que o problema tem no máximo uma tarefa ou nenhuma tarefa, o problema da promessa é chamado . O teorema de Valiant – Vazirani afirma que, se houver um algoritmo de tempo polinomial para , então . Para provar seu teorema, eles mostraram que o problema da promessa é -hard sob reduções de tempo polinomiais aleatórias. Um corolário que se segue do teorema de Valiant – Vazirani é que está completo para sob reduções de tempo polinomiais aleatórias.SAT INAMBIGUOUSSAT INAMBIGUOUSNP=RPSAT INAMBIGUOUSNPUNIQUE-SATDp


[1] Papadimitriou, Christos H. e Mihalis Yannakakis. "A complexidade das facetas (e algumas facetas da complexidade)." Anais do décimo quarto simpósio anual da ACM sobre Teoria da Computação. ACM, 1982.

[2] Blass, Andreas e Yuri Gurevich. "Sobre o único problema de satisfação." Information and Control 55.1 (1982): 80-88.

[3] Valiant, Leslie G. e Vijay V. Vazirani. "O NP é tão fácil quanto detectar soluções exclusivas". Teórico Computer Science 47 (1986): 85-93.

Juho
fonte
Obrigado pela resposta; Eu também encontrei um capítulo em um livro dizendo que a existência de uma redução determinística está aberta.
Sdcvvc