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

Problem decyzyjny

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

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?$\Delta_2$$\mathsf{UP}$$\mathsf{coNP}$

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 2 ∈ N P } .$\text{UNIQUE-SAT}$$\mathsf{US}$$\mathsf{D^p}$$\mathsf{D^p}$$\mathsf{D^p} = \{ L_1 \cap \overline{L_2} \mid L_1,L_2 \in \mathsf{NP} \}$

$\mathsf{D^p}$$\mathsf{D^p}$$L_1$$L_2$$2$$\mathsf{D^p}$$\text{UNIQUE-SAT}$$\text{SAT}$$\mathsf{D^p}$$\text{UNIQUE-SAT}$

$\text{UNAMBIGUOUS-SAT}$$\text{UNAMBIGUOUS-SAT}$$\mathsf{NP}=\mathsf{RP}$$\text{UNAMBIGUOUS-SAT}$$\mathsf{NP}$$\text{UNIQUE-SAT}$$\mathsf{D^p}$

[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.