Name
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. |
Year | Venue | Keywords |
|---|---|---|
1986 | Proc. of the conference on Structure in complexity theory | np predicate,common class,richer perspective,immunity result,results present new idea,boolean hierarchy,boolean operation,complete language,complementary class,previous result,technical report,computer science |
Field | DocType | Volume |
Polynomial hierarchy,Discrete mathematics,Boolean circuit,Boolean satisfiability problem,Boolean algebra,Boolean hierarchy,Computer hardware,And-inverter graph,Boolean expression,Circuit minimization for Boolean functions,Mathematics | Conference | 223 |
ISSN | ISBN | Citations |
0302-9743 | 0-387-16486-3 | 44 |
PageRank | References | Authors |
8.97 | 18 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jin-Yi Cai | 1 | 2327 | 239.71 |
| L Hemachandra | 2 | 106 | 14.12 |