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)
collapsecomputational complexityadviceBoolean hierarchyBoolean highnessBoolean lownesshardeasyhighnesslownesspolynomial-time hierarchy
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
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