On Unique Satisfiability and the Threshold Behavior of Randomized Reductions
On Unique Satisfiability and the Threshold Behavior of Randomized Reductions
复制标题
关于唯一可满足性和随机归约的阈值行为
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
P. Rohatgi
中科院分区：
文献类型：
--
作者：
Richard Chang;Jim Kadin;P. Rohatgi
本文提出的研究是由关于独特可满足问题的复杂性的一些新结果的动机。这些结果是在论文中首次显示的，是：？如果USAT？ ，然后d = co-d和pH崩溃。 co-d，然后pH崩溃。这些结果的证据仅使用以下事实：在随机降低下，DP完成了USAT，即使这些降低的概率可能较低，但即使是较低的事实。此外，这些结果表明，USAT和DP的结构复杂性非常相似，因此它们为即使在“弱”随机降低下完成的集合都可以捕获多个属性的论点提供支持。完整的集合。但是，在这些“弱”随机减少的情况下，psatlog n]也是完整的，在这种情况下，USAT并未捕获集合的属性，用于PSATLOG N]。为了解释这一异常，开发了随机减少的阈值行为的概念。为NP，Co-NP，DP和Co-DP显示了阈值的紧密边界。此外，可以将这些结果推广到布尔层次结构的阈值上的上限和下限。这些上限以斐波那契数表示。
The research presented in this paper is motivated by the some new results on the complexity of the unique satisfiability problem, USAT. These results, which are shown for the first time in the paper, are: ?if USAT ? , then D = co-D and PH collapses.?if USAT ? co-D, then PH collapses.?if USAT has OR, then PH collapses. The proofs of these results use only the fact that USAT is complete for DP under randomized reductions-even though the probability bound of these reductions may be low. Furthermore, these results show that the structural complexity of USAT and of DP many-one complete sets are very similar, and so they lend support to the argument that even sets complete under "weak" randomized reductions can capture the properties of the many-one complete sets. However, under these "weak" randomized reductions, USAT is complete for PSATlog n] as well, and in this case, USAT does not capture the properties of the sets many-one complete for PSATlog n]. To explain this anomaly, the concept of the threshold behavior of randomized reductions is developed. Tight bounds on the thresholds are shown for NP, co-NP, DP, and co-DP. Furthermore, these results can be generalized to give upper and lower bounds on the thresholds for the Boolean hierarchy. These upper bounds are expressed in terms of Fibonacci numbers.