On boolean lowness and boolean highness

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)

zbMATH Keywords

collapsecomputational complexityadviceBoolean hierarchyBoolean highnessBoolean lownesshardeasyhighnesslownesspolynomial-time hierarchy

Mathematics Subject Classification ID

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