Two queries

zbMath0947.68064MaRDI QIDQ1961371

Harry Buhrman, Lance J. Fortnow

Publication date: 17 January 2000

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

queries \({\mathbf S}{\mathbf A}{\mathbf T}\)

Mathematics Subject Classification ID

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

Related Items

The 1-Versus-2 Queries Problem Revisited, The 1-versus-2 queries problem revisited, An oracle builder's toolkit, Some connections between bounded query classes and non-uniform complexity., Commutative queries, Proving SAT does not have small circuits with an application to the two queries problem

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
• The complexity of optimization problems
• Probabilistic quantifiers and games
• On 1-truth-table-hard languages
• Observations on measure and lowness for \(\Delta_ 2^ p\)
• The isomorphism conjecture holds and one-way functions exist relative to an oracle
• Commutative queries
• Oracles and queries that are sufficient for exact learning
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• A Downward Collapse within the Polynomial Hierarchy
• On computing Boolean connectives of characteristic functions
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• A relationship between difference hierarchies and relativized polynomial hierarchies