Two queries

MaRDI QIDQ1961371zbMATH OpenFDO

Authors Harry Buhrman, Lance 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

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

Recommendations

• scientific article; zbMATH DE number 1335876
• Bounded queries to SAT and the Boolean hierarchy
• The 1-Versus-2 Queries Problem Revisited
• Proving SAT does not have small circuits with an application to the two queries problem
• The two queries assumption and Arthur-Merlin classes

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1304327 (Why is no real title available?)
• scientific article; zbMATH DE number 1555957 (Why is no real title available?)
• scientific article; zbMATH DE number 1775405 (Why is no real title available?)
• A Downward Collapse within the Polynomial Hierarchy
• A relationship between difference hierarchies and relativized polynomial hierarchies
• Commutative queries
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Observations on measure and lowness for \(\Delta_ 2^ p\)
• On 1-truth-table-hard languages
• On computing Boolean connectives of characteristic functions
• Oracles and queries that are sufficient for exact learning
• Probabilistic quantifiers and games
• Some consequences of non-uniform conditions on uniform classes
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The complexity of optimization problems
• The isomorphism conjecture holds and one-way functions exist relative to an oracle

Cited in

(8)

• The 1-Versus-2 Queries Problem Revisited
• 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
• scientific article; zbMATH DE number 2080645 (Why is no real title available?)

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)