The Boolean hierarchy of NP-partitions

DOI10.1016/j.ic.2007.06.003zbMath1146.68375OpenAlexW2034858926MaRDI QIDQ924719

Sven Kosub, Klaus W. Wagner

Publication date: 19 May 2008

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2007.06.003

zbMATH Keywords

partitionsBoolean hierarchypolynomial hierarchycomputational complexity theoryorders and lattices

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Fine hierarchies via Priestley duality

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some consequences of non-uniform conditions on uniform classes
• On self-reducibility and weak P-selectivity
• NP-partitions over posets with an application to reducing the set of solutions of NP problems
• The difference and truth-table hierarchies for NP
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The Boolean Hierarchy I: Structural Properties
• NONDETERMINISTICALLY SELECTIVE SETS
• Computing Solutions Uniquely Collapses the Polynomial Hierarchy
• The complexity theory companion
• On boolean lowness and boolean highness

This page was built for publication: The Boolean hierarchy of NP-partitions