On boolean lowness and boolean highness
From MaRDI portal
Publication:5941441
DOI10.1016/S0304-3975(00)00146-8zbMath0974.68064MaRDI QIDQ5941441
Klaus W. Wagner, Steffen Reith
Publication date: 20 August 2001
Published in: Theoretical Computer Science (Search for Journal in Brave)
collapse; computational complexity; advice; Boolean hierarchy; Boolean highness; Boolean lowness; hardeasy; highness; lowness; polynomial-time hierarchy
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
The Boolean hierarchy of NP-partitions, Generalized modal satisfiability, A note on parallel queries and the symmetric-difference hierarchy.
Cites Work
- Unnamed Item
- Unnamed Item
- A low and a high hierarchy within NP
- The difference and truth-table hierarchies for NP
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- The Boolean Hierarchy I: Structural Properties
- Minimal pairs and high recursively enumerable degrees
- Automorphisms of the lattice of recursively enumerable sets
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- A relationship between difference hierarchies and relativized polynomial hierarchies