Complexité de décider si une formule a exactement 1 affectation satisfaisante

Le problème de décision

Étant donné une formule booléenne , ϕ a-t-il exactement une affectation satisfaisante?$\phi$$\phi$

peut être vu comme étant en , U P -hard et c o N P -hard. En sait-on plus sur sa complexité?$\Delta_2$$\mathsf{UP}$$\mathsf{coNP}$

Votre problème est connu sous le nom de problème qui est U S- complet. Le problème est dans D p mais n'est pas connu pour être D p- dur sous des réductions de temps polynomiales déterministes, où la classe 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. et Mihalis Yannakakis. "La complexité des facettes (et certaines facettes de la complexité)." Actes du quatorzième symposium annuel de l'ACM sur la théorie de l'informatique. ACM, 1982.

[2] Blass, Andreas et Yuri Gurevich. "Sur le problème de satisfiabilité unique." Information et contrôle 55.1 (1982): 80-88.

[3] Valiant, Leslie G. et Vijay V. Vazirani. "NP est aussi simple que de détecter des solutions uniques." Informatique théorique 47 (1986): 85-93.