On Unique Satisfiability and the Threshold Behavior of Randomized Reductions

摘要

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 PSAT[log n] as well, and in this case, USAT does not capture the properties of the sets many-one complete for PSAT[log 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.