Bounded queries, approximations, and the Boolean hierarchy

DOI10.1006/INCO.2000.2884MaRDI QIDQ1854449zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Bounded queries to SAT and the Boolean hierarchy
• On the Structure of Bounded Queries to Arbitrary NP Sets
• Bounded Query Classes
• On Bounded Queries and Approximation
• Structure in Approximation Classes

Cites work

• A Downward Collapse within the Polynomial Hierarchy
• A relationship between difference hierarchies and relativized polynomial hierarchies
• Bounded queries to SAT and the Boolean hierarchy
• Bounded Query Classes
• Complexity-Restricted Advice Functions
• Derandomized graph products
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 4033067 (Why is no real title available?)
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 1256635 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 1335876 (Why is no real title available?)
• scientific article; zbMATH DE number 709537 (Why is no real title available?)
• scientific article; zbMATH DE number 2077131 (Why is no real title available?)
• On Bounded Queries and Approximation
• On computing Boolean connectives of characteristic functions
• On Restricting the Size of Oracles Compared with Restricting Access to Oracles
• On the query complexity of clique size and maximum satisfiability
• On the ratio of optimal integral and fractional covers
• Quantitative Relativizations of Complexity Classes
• Some consequences of non-uniform conditions on uniform classes
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• The complexity of facets (and some facets of complexity)
• The complexity of optimization problems
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The strong exponential hierarchy collapses

Cited in

(9)

• Boolean query optimization and the 0-1 hyperbolic sum problem
• Competing provers yield improved Karp-Lipton collapse results
• On the computational complexity of querying bounds on differences constraints
• A note on parallel queries and the symmetric-difference hierarchy.
• 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 1405575 (Why is no real title available?)
• scientific article; zbMATH DE number 1424049 (Why is no real title available?)
• First-order queries on structures of bounded degree are computable with constant delay

This page was built for publication: Bounded queries, approximations, and the Boolean hierarchy

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