On the Structure of NP Computations under Boolean Operators
- Author: R. Chang.
- Cite as: PhD Thesis, Cornell University, August 1991.
Note: All the results in this thesis have appeared in separate
journal papers.
- Most readable version: Cornell University Computer Science
Technical Report TR 91-1244.
- Status: complete.
- Online:
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, AND2
and OR2.
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.
Last Modified:
2 Jun 2008 22:47:13 EDT
by
Richard Chang