On unique satisfiability and the threshold behavior of randomized reductions. (English) Zbl 0837.68026

Summary: 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:
\(\bullet\) if \(\text{USAT} \equiv^P_m \overline {\text{USAT}}\), then \(\text{D}^{\text{P}}= \text{co-D}^{\text{P}}\) and PH collapses.
\(\bullet\) if \(\text{USAT} \in \text{co-D}^{\text{P}}\), then PH collapses.
\(\bullet\) if USAT has \(\text{OR}_\omega\), then PH collapses.
The proofs of these results use only the fact that USAT is complete for \(\text{D}^{\text{P}}\) 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 \(\text{D}^{\text{P}}\) 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 \(\text{P}^{\text{SAT} [\log n]}\) as well, and in this case, USAT does not capture the properties of the sets many-one complete for P\(^{\text{SAT} [\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, \(\text{D}^{\text{P}}\), and \(\text{co-D}^{\text{P}}\). 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.


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68N99 Theory of software
Full Text: DOI Link