Bounded queries, approximations, and the Boolean hierarchy

DOI10.1006/inco.2000.2884zbMath1007.68072OpenAlexW2031104867MaRDI QIDQ1854449

Richard Chang

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.2000.2884

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Competing provers yield improved Karp-Lipton collapse results ⋮ A note on parallel queries and the symmetric-difference hierarchy.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong exponential hierarchy collapses
• Some consequences of non-uniform conditions on uniform classes
• The complexity of facets (and some facets of complexity)
• The complexity of optimization problems
• Bounded queries to SAT and the Boolean hierarchy
• On the ratio of optimal integral and fractional covers
• On the query complexity of clique size and maximum satisfiability
• Derandomized graph products
• Bounded Query Classes
• On Restricting the Size of Oracles Compared with Restricting Access to Oracles
• Quantitative Relativizations of Complexity Classes
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• A Downward Collapse within the Polynomial Hierarchy
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Complexity-Restricted Advice Functions
• On Bounded Queries and Approximation
• 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: Bounded queries, approximations, and the Boolean hierarchy