On The Structure Of NP Computations Under Boolean Operators
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
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