On the Structure of Bounded Queries to Arbitrary NP Sets

DOI10.1137/0221045MaRDI QIDQ4016404zbMATH OpenOpenAlexFDO

Authors Richard Chang

Publication date 14 December 1992

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://hdl.handle.net/1813/6784

zbMATH Keywords

Boolean hierarchybounded queriesnonuniform computationpolynomial-time hierarchysparse sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Bounded queries to SAT and the Boolean hierarchy
• scientific article; zbMATH DE number 1304327
• On bounded query machines
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• Bounded queries to arbitrary sets

Cited in

(17)

• On bounded query machines
• Bounded queries to SAT and the Boolean hierarchy
• Bounding queries in the analytic polynomial-time hierarchy
• Some connections between bounded query classes and non-uniform complexity.
• Bounded queries, approximations, and the Boolean hierarchy
• On the computational complexity of querying bounds on differences constraints
• Proving SAT does not have small circuits with an application to the two queries problem
• scientific article; zbMATH DE number 4137760 (Why is no real title available?)
• On the convergence of query-bounded computations and logical closure properties of c.e. sets
• On Bounded Queries and Approximation
• scientific article; zbMATH DE number 1114037 (Why is no real title available?)
• Bounded queries to arbitrary sets
• A downward translation in the polynomial hierarchy
• First-order queries on structures of bounded degree are computable with constant delay
• NP search problems in low fragments of bounded arithmetic
• A finite model-theoretical proof of a property of bounded query classes within PH
• On the asymmetric complexity of the group-intersection problem

This page was built for publication: On the Structure of Bounded Queries to Arbitrary NP Sets

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