Show simple item record

dc.contributor.authorChang, Richarden_US
dc.contributor.authorKadin, Jimen_US
dc.description.abstractThis 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.extent1200236 bytes
dc.format.extent271744 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleOn the Structure of Uniquely Satisfiable Formulasen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record