dc.contributor.author Chang, Richard en_US dc.contributor.author Kadin, Jim en_US dc.date.accessioned 2007-04-23T17:47:24Z dc.date.available 2007-04-23T17:47:24Z dc.date.issued 1990-05 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1124 en_US dc.identifier.uri https://hdl.handle.net/1813/6964 dc.description.abstract This paper presents some new results on the computational complexity of the set of uniquely satisfiable Boolean formulas (USAT). Valiant and Vazirani showed that USAT is complete for the class $D^{P}$ under randomized reductions. In spite of the fact that the probability bound of this reduction is low, we show that USAT captures many properties possessed by $D^{P}$ many-one complete sets. We show that the structure of USAT can affect the structure of $D^{P}$ and the entire Polynomial Hierarchy (PH) as well. That is, 1. if USAT $\equiv^{P}_{m} \overline{USAT}$, then $D^{P}$ = co-$D^{P}$ and PH collapses. 2. if USAT $\in$ co-$D^{P}$, then PH collapses. 3. if USAT is closed under disjunctive reductions, then PH collapses. The third result implies that the probability bound in the Valiant-Vazirani reduction cannot be amplified by repeated trials unless the Polynomial Hierarchy collapses. These results show that even sets complete under "weak" randomized reductions can capture properties of many-one complete sets. en_US dc.format.extent 1200236 bytes dc.format.extent 271744 bytes dc.format.mimetype application/pdf dc.format.mimetype application/postscript dc.language.iso en_US en_US dc.publisher Cornell University en_US dc.subject computer science en_US dc.subject technical report en_US dc.title On the Structure of Uniquely Satisfiable Formulas en_US dc.type technical report en_US
﻿