eCommons

 

On The Structure Of NP Computations Under Boolean Operators

Other Titles

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.

Journal / Series

Volume & Issue

Description

Sponsorship

Date Issued

1991-11

Publisher

Cornell University

Keywords

computer science; technical report

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1244

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record