The Boolean hierarchy: Hardware over NP. (English) Zbl 0611.68018

Structure in complexity theory, Proc. Conf., Berkeley/Calif. 1986, Lect. Notes Comput. Sci. 223, 105-124 (1986).
[For the entire collection see Zbl 0591.00015.]
In this paper, wer study the complexity of sets formed by boolean operations (\(\cup,\cap\), 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\) is a richer perspective. Throughout, we emphasize the structure of the boolean hierarchy and its relations with more common classes.


68Q25 Analysis of algorithms and problem complexity


Zbl 0591.00015