On Boolean lowness and Boolean highness

DOI10.1007/3-540-68535-9_18MaRDI QIDQ4218416zbMATH OpenFDO

Authors S. Reith, K. W. Wagner

Publication date 18 May 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-68535-9_18

zbMATH Keywords

complexity theoryhighnesslowness

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On boolean lowness and boolean highness
• The Boolean Hierarchy I: Structural Properties
• Generalized lowness and highness and probabilistic complexity classes
• scientific article; zbMATH DE number 3988706

Cited in

(10)

• Boolean operations, joins, and the extended low hierarchy
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• scientific article; zbMATH DE number 1008510 (Why is no real title available?)
• Generalized lowness and highness and probabilistic complexity classes
• Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
• Lowness results: the next generation
• On boolean lowness and boolean highness
• Intersection suffices for Boolean hierarchy equivalence
• The join can lower complexity

This page was built for publication: On Boolean lowness and Boolean highness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4218416)