Commutative queries
type: Item
instance of: scholarly article
title: Commutative queries
zbMATH Open document ID: 1007.03040
author: Richard Beigel
author: Richard Chang
published in: Information and Computation
publication date: 2003-01-14T00:00:00Z
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 03B25
zbMATH DE Number: 1853169
zbMATH Keywords: polynomial-time Turing machines
zbMATH Keywords: order of oracle queries
zbMATH Keywords: polynomial hierarchy
zbMATH Keywords: decision problems
MaRDI profile type: Publication
full work available at URL: inco.2000.2918
OpenAlex ID: W2913917660
cites work: Quasi-linear truth-table reductions to \(p\)-selective sets
cites work: A relationship between difference hierarchies and relativized polynomial hierarchies
cites work: Bounded queries to SAT and the Boolean hierarchy
cites work: Two queries
cites work: Approximable sets
cites work: The Boolean Hierarchy I: Structural Properties
cites work: The Boolean Hierarchy II: Applications
cites work: On computing Boolean connectives of characteristic functions
cites work: The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
cites work: Q4520757
cites work: A Downward Collapse within the Polynomial Hierarchy
cites work: Query Order
cites work: Q4281521
cites work: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
cites work: On the commutativity of jumps
cites work: Polynomial-Time Membership Comparable Sets
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.2918
description: scientific article; zbMATH DE number 1853169