A note on parallel queries and the symmetric-difference hierarchy.

DOI10.1016/S0020-0190(98)00024-6zbMath1078.68636OpenAlexW2090171172MaRDI QIDQ2583533

Klaus W. Wagner

Publication date: 17 January 2006

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(98)00024-6

zbMATH Keywords

Boolean hierarchyParallel queriesPlus hierarchyQuery orderSymmetric-difference hierarchy

Mathematics Subject Classification ID

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

Related Items (5)

Fine hierarchies via Priestley duality ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ SELF-SPECIFYING MACHINES ⋮ A reducibility for the dot-depth hierarchy ⋮ Reducing the number of solutions of NP functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• More complicated questions about maxima and minima, and some closures of NP
• Bounded queries to SAT and the Boolean hierarchy
• The polynomial-time hierarchy
• Bounded queries, approximations, and the Boolean hierarchy
• Bounded Query Classes
• The difference and truth-table hierarchies for NP
• The Boolean Hierarchy I: Structural Properties
• Query Order
• Query order in the polynomial hierarchy
• A relationship between difference hierarchies and relativized polynomial hierarchies
• On boolean lowness and boolean highness

This page was built for publication: A note on parallel queries and the symmetric-difference hierarchy.