Pinpointing computation with modular queries in the Boolean hierarchy

DOI10.1007/3-540-62034-6_60MaRDI QIDQ6567782zbMATH OpenFDO

Authors Manindra Agrawal, Richard Beigel, Thomas Thierauf

Publication date 5 July 2024

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Bounded queries to SAT and the Boolean hierarchy
• Query Order
• Bounded Query Classes
• The Boolean Hierarchy I: Structural Properties
• Restricted information from nonadaptive queries to NP

Cites work

• scientific article; zbMATH DE number 3930351 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• A comparison of polynomial time reducibilities
• Bounded Query Classes
• Bounded queries to SAT and the Boolean hierarchy
• Complexity-Restricted Advice Functions
• The Boolean Hierarchy I: Structural Properties
• The difference and truth-table hierarchies for NP

This page was built for publication: Pinpointing computation with modular queries in the Boolean hierarchy

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