Two queries
From MaRDI portal
zbMATH Open0947.68064MaRDI QIDQ1961371FDOQ1961371
Authors: Harry Buhrman, Lance Fortnow
Publication date: 17 January 2000
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Recommendations
Cites Work
- Title not available (Why is that?)
- The complexity of optimization problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Oracles and queries that are sufficient for exact learning
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- Some consequences of non-uniform conditions on uniform classes
- On computing Boolean connectives of characteristic functions
- On 1-truth-table-hard languages
- Observations on measure and lowness for \(\Delta_ 2^ p\)
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Title not available (Why is that?)
- Probabilistic quantifiers and games
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- A Downward Collapse within the Polynomial Hierarchy
- A relationship between difference hierarchies and relativized polynomial hierarchies
- Title not available (Why is that?)
- The isomorphism conjecture holds and one-way functions exist relative to an oracle
- Title not available (Why is that?)
- Commutative queries
Cited In (8)
- Commutative queries
- The 1-versus-2 queries problem revisited
- Proving SAT does not have small circuits with an application to the two queries problem
- Complexity classes of equivalence problems revisited
- Some connections between bounded query classes and non-uniform complexity.
- An oracle builder's toolkit
- Title not available (Why is that?)
- The 1-Versus-2 Queries Problem Revisited
This page was built for publication: Two queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1961371)