Show simple item record

dc.contributor.authorChang, Richarden_US
dc.description.abstractThis 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.en_US
dc.format.extent7781410 bytes
dc.format.extent1320920 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleOn The Structure Of NP Computations Under Boolean Operatorsen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record