JavaScript is disabled for your browser. Some features of this site may not work without it.
The Boolean Hierarchy: Hardware over NP

Author
Cai, Jin-yi; Hemachandra, Lane A.
Abstract
In this paper, we study the complexity of sets formed by boolean operations $(\bigcup, \bigcap,$ and complementation) on NP sets. These are the sets accepted by trees of hardware with NP predicates as leaves, and together form the boolean hierarchy. We present many results about the boolean hierarchy: separation and immunity results, complete languages, upward separations, connections to sparse oracles for NP, and structural asymmetries between complementary classes. Some results present new ideas and techniques. Others put previous results about NP and $D^{P}$ in a richer perspective. Throughout, we emphasize the structure of the boolean hierarchy and its relations with more common classes.
Date Issued
1985-12Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR85-724
Type
technical report