Złożoność decydowania, czy formuła ma dokładnie 1 zadowalające zadanie

11

Problem decyzyjny

Biorąc pod uwagę logiczną formułę , czy ϕ ma dokładnie jedno zadowalające zadanie?ϕϕ

mogą być widoczne w , U P -hard i c o N P -hard. Czy jest coś bardziej znanego na temat jego złożoności?Δ2UPcoNP

sdcvvc
źródło

Odpowiedzi:

11

Problem jest znany jako problem, który jest U S -Complete. Problemem jest D p , ale nie wiadomo, D P -hard pod deterministycznych wielomianowych ograniczenia czasowe, w którym grupa D P = { l 1Ż L 2 | L 1 , L 2N P } .UNIQUE-SATUSDpDpDp={L1L2¯L1,L2NP}

DpDpL1L22DpUNIQUE-SATSATDpUNIQUE-SAT

UNAMBIGUOUS-SATUNAMBIGUOUS-SATNP=RPUNAMBIGUOUS-SATNPUNIQUE-SATDp


[1] Papadimitriou, Christos H. i Mihalis Yannakakis. „Złożoność aspektów (i niektóre aspekty złożoności)”. Materiały z czternastego dorocznego sympozjum ACM na temat teorii obliczeń. ACM, 1982.

[2] Blass, Andreas i Jurij Gurewicz. „O wyjątkowym problemie satysfakcji”. Information and Control 55.1 (1982): 80-88.

[3] Valiant, Leslie G. i Vijay V. Vazirani. „NP jest tak łatwe, jak wykrywanie unikalnych rozwiązań”. Theoretical Computer Science 47 (1986): 85-93.

Juho
źródło
Dziękuję za odpowiedź; Znalazłem także rozdział w książce , w którym napisano, że istnienie deterministycznej redukcji jest otwarte.
sdcvvc