# The Boolean Hierarchy II: Applications

@article{Cai1989TheBH, title={The Boolean Hierarchy II: Applications}, author={Jin-Yi Cai and Thomas Gundermann and Juris Hartmanis and Lane A. Hemaspaandra and Vivian Sewelson and Klaus W. Wagner and Gerd Wechsung}, journal={SIAM J. Comput.}, year={1989}, volume={18}, pages={95-111} }

The Boolean Hierarchy I: Structural Properties [J. Cai et al., SIAM J. Comput ., 17 (1988), pp. 1232–252] explores the structure of the boolean hierarchy, the closure of NP with respect to boolean ...

#### Topics from this paper

#### 124 Citations

Intersection Suffices for Boolean Hierarchy Equivalence

- Mathematics, Computer Science
- COCOON
- 1995

It is proved that these equalities hold for any complexity class closed under intersection, and that for any class C closed under union and intersection, the Boolean closure of C,The Boolean hierarchy over C, and the symmetric difference hierarchy overC all are equal. Expand

COMPLEXITY CLASSIFICATIONS FOR DIFFERENT EQUIVALENCE AND AUDIT PROBLEMS FOR BOOLEAN CIRCUITS

- Mathematics, Computer Science
- 2012

For a number of restricted sets of gate types (bases) the authors obtain efficient algorithms, while for all other gate types it is shown these problems are at least NP-hard. Expand

A Machine Model for the Complexity of NP-Approximation Problems

- Mathematics, Computer Science
- Current Trends in Theoretical Computer Science
- 2001

This paper investigates a machine-based model for the complexity of approximating the CLIQUE problem. The model consists of nondeterministic polynomial time Turing machines with limited access to an… Expand

Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets

- Mathematics, Computer Science
- SIAM J. Comput.
- 1997

It is shown that two hierarchies---the Hausdorff hierarchy and the nested difference hierarchy---which in the NP case are equal to the Boolean closure fail to be equal for the UP case in some relativized worlds, and it is proved that closure under union is not needed for this claim. Expand

Introduction to the theory of complexity

- Mathematics, Computer Science
- Prentice Hall international series in computer science
- 1994

1. Mathematical Preliminaries, Elements of Computability Theory, and Space-Complexity Classes: Algorithms and Complexity Classes. Expand

Structure of Complexity Classes: Separations, Collapses, and Completeness

- Mathematics
- 1988

During the last few years, unprecedented progress has been made in structural complexity theory; class inclusions and relativized separations were discovered, and hierarchies collapsed. We survey… Expand

A survey on counting classes

- Mathematics, Computer Science
- Proceedings Fifth Annual Structure in Complexity Theory Conference
- 1990

The authors prove P/sup EP(log)/ 25 PP, investigate the Boolean closure BC( EP) of EP, and give a relativization principle which allows them to completely separate BC(EP) in a suitable relativized world and to give simple proofs for known relativizing results. Expand

Much ado about functions

- Computer Science, Mathematics
- Proceedings of Computational Complexity (Formerly Structure in Complexity Theory)
- 1996

This paper surveys basic results on complexity classes of partial multivalued functions. We stress basic inclusion relations, interesting hierarchies, and results that demonstrate that hierarchies… Expand

On the Power of Parity Polynomial Time

- Mathematics, Computer Science
- STACS
- 1989

This paper proves that the complexity class ⊕P, parity polynomial time [PZ83], contains the class of languages accepted by NP machines with few accepting paths. Indeed, ⊕P contains a broad class of… Expand

On High and Low Sets for the Boolean Hierarchy

- Mathematics
- 2007

The polynomial-time hierarchy (PH) is central for many considerations of complexity theory. We call a set A 2 NP high (low, resp.) for the class p k of the polynomial-time hierarchy if p k… Expand