On Unique Satisfiability and the Threshold Behavior of Randomized Reductions
Richard Chang, Jim Kadin, Pankaj Rohatgi · Journal of Computer and System Sciences · 1995
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.