Title:	On The Structure Of NP Computations Under Boolean Operators
Authors:	Chang, Richard
Keywords:	computer science technical report
Issue Date:	Nov-1991
Publisher:	Cornell University
Citation:	http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1244
Abstract:	This thesis is mainly concerned with the structural complexity of the Boolean Hierarchy. The Boolean Hierarchy is composed of complexity classes constructed using Boolean operators on NP computations. The thesis begins with a description of the role of the Boolean Hierarchy in the classification of the complexity of NP optimization problems. From there, the thesis goes on to motivate the basic definitions and properties of the Boolean Hierarchy. Then, these properties are shown to depend only on the closure of NP under the Boolean operators, AND$_{2}$ and OR$_{2}$. A central theme of this thesis is the development of the hard/easy argument which shows intricate connections between the Boolean Hierarchy and the Polynomial Hierarchy. The hard/easy argument shows that the Boolean Hierarchy cannot collapse unless the Polynomial Hierarchy also collapses. The results shown in this regard are improvements over those previously shown by Kadin. Furthermore, it is shown that the hard/easy argument can be adapted for Boolean hierarchies over incomplete NP languages. That is, under the assumption that certain incomplete languages exist, the Boolean hierarchies over those languages must be proper (infinite) hierarchies. Finally, this thesis gives an application of the hard/easy argument to resolve the complexity of a natural problem - the unique satisfiability problem. This last refinement of the hard/easy argument also points out some long-ignored issues in the definition of randomized reductions.
URI:	http://hdl.handle.net/1813/7084
Appears in Collections:	Computer Science Technical Reports

Files in This Item: File Description Size Format 91-1244.pdf 7.6 MB Adobe PDF View/Open 91-1244.ps 1.29 MB Postscript View/Open

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.