Bounded queries, approximations, and the Boolean hierarchy
type: Item
instance of: scholarly article
title: Bounded queries, approximations, and the Boolean hierarchy
zbMATH Open document ID: 1007.68072
author: Richard Chang
published in: Information and Computation
publication date: 2003-01-14T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 1853194
MaRDI profile type: Publication
full work available at URL: inco.2000.2884
OpenAlex ID: W2031104867
cites work: Derandomized graph products
cites work: Q4230322
cites work: Q4230321
cites work: A relationship between difference hierarchies and relativized polynomial hierarchies
cites work: Q3996675
cites work: Bounded queries to SAT and the Boolean hierarchy
cites work: Q4258567
cites work: Quantitative Relativizations of Complexity Classes
cites work: Q3773331
cites work: The Boolean Hierarchy I: Structural Properties
cites work: The Boolean Hierarchy II: Applications
cites work: On Bounded Queries and Approximation
cites work: Q4318988
cites work: On the query complexity of clique size and maximum satisfiability
cites work: On computing Boolean connectives of characteristic functions
cites work: The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
cites work: Q4470516
cites work: The strong exponential hierarchy collapses
cites work: A Downward Collapse within the Polynomial Hierarchy
cites work: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
cites work: The complexity of optimization problems
cites work: Complexity-Restricted Advice Functions
cites work: On Restricting the Size of Oracles Compared with Restricting Access to Oracles
cites work: On the ratio of optimal integral and fractional covers
cites work: Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
cites work: Q3221403
cites work: The complexity of facets (and some facets of complexity)
cites work: Bounded Query Classes
cites work: Some consequences of non-uniform conditions on uniform classes
DOI: 10.1006/INCO.2000.2884
description: scientific article; zbMATH DE number 1853194