确定公式是否完全满足作业的复杂性

Question

决策问题

给定布尔公式$ phi $，$ phi $有一个令人满意的作业吗？

可以看到$ delta_2 $，$ mathsf {up} $ - 硬和$ mathsf {conp} $ - 硬。对其复杂性有什么了解吗？

Answer 1

您的问题称为$ text {unique-sat} $问题，即$ mathsf {us} $ - 完整。问题是在$ mathsf {d^p} $中，但不知道是$ mathsf {d^p} $ - 在确定性的多项式减少下硬，其中类$ mathsf {d^p} = {l_1 cap edimine {l_2} mid l_1，l_2 in mathsf {np} } $。

Papadimitriou和Yannakis [1]表明，$ Mathsf {d^p} $中包含的唯一令人满意的公式集。随之而来的是$ mathsf {d^p} $的定义：让$ l_1 $为sat，让$ l_2 $为具有$ 2 $或更多令人满意的作业的一组公式。关于$ mathsf {d^p} $ - $ text {unique sat} $的硬度，blass and gurevich [2]给出了部分答案。首先，他们表现出一种不归功于证明技术来解决问题。但是，Valiant和Vazirani [3]从$ text {sat} $中缩减了随机多项式时间，显示$ mathsf {d^p} $ - $ text {unique sat} $的硬度在随机多项式时间减少下。

当知道该问题最多有一个分配或没有作业时，承诺问题称为$ text {unmambiguul-sat} $。 Valiant-vazirani定理指出，如果有$ text {unmambiguul-sat} $的多项式时间算法，则$ mathsf {np} = mathsf {rp} $。为了证明他们的定理，他们证明了承诺问题$ text {unmambux-sat} $是$ mathsf {np} $ - 在随机多项式时间减少下硬。来自英勇– Vazirani定理的推论是，在随机多项式时间缩短下，$ text {unique sat} $对于$ mathsf {d^p} $是完整的。

---

1] Papadimitriou，Christos H.和Mihalis Yannakakis。 “方面的复杂性（以及复杂性的一些方面）。”第十四届年度ACM计算理论研讨会论文集。 ACM，1982。

[2] Blass，Andreas和Yuri Gurevich。 “关于独特的满足问题。”信息与控制55.1（1982）：80-88。

[3] Valiant，Leslie G.和Vijay V. Vazirani。 “ NP就像检测独特的解决方案一样容易。”理论计算机科学47（1986）：85-93。