Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. On the Structure of Uniquely Satisfiable Formulas

On the Structure of Uniquely Satisfiable Formulas

File(s)
90-1124.ps (265.38 KB)
90-1124.pdf (1.14 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6964
Collections
Computer Science Technical Reports
Author
Chang, Richard
Kadin, Jim
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.

Date Issued
1990-05
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1124
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance