Two queries
From MaRDI portal
Publication:1961371
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)
Related Items (7)
An oracle builder's toolkit ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ The 1-Versus-2 Queries Problem Revisited ⋮ Proving SAT does not have small circuits with an application to the two queries problem ⋮ The 1-versus-2 queries problem revisited ⋮ Complexity classes of equivalence problems revisited ⋮ Commutative queries
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
This page was built for publication: Two queries
