Some connections between bounded query classes and non-uniform complexity.
type: Item
instance of: scholarly article
title: Some connections between bounded query classes and non-uniform complexity.
zbMATH Open document ID: 1058.68056
DOI: 10.1016/S0890-5401(03)00091-9
author: Amihood Amir
author: Richard Beigel
author: William Gasarch
published in: Information and Computation
publication date: 2004-03-14T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 2056454
MaRDI profile type: Publication
cites work: Quasi-linear truth-table reductions to \(p\)-selective sets
cites work: Polynomial terse sets
cites work: The polynomial-time hierarchy and sparse oracles
cites work: Sparse Sets, Lowness and Highness
cites work: Q4259996
cites work: Bounded queries to SAT and the Boolean hierarchy
cites work: Terse, superterse, and verbose sets
cites work: The complexity of ODDnA
cites work: Approximable sets
cites work: Quantifying the amount of verboseness
cites work: Q3097395
cites work: The global power of additional queries to random oracles
cites work: On Sets Truth-Table Reducible to Sparse Sets
cites work: Q4385519
cites work: Two queries
cites work: Lower bounds for constant-depth circuits in the presence of help bits
cites work: Enumerative counting is hard
cites work: A note on enumerative counting
cites work: On the Structure of Bounded Queries to Arbitrary NP Sets
cites work: The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
cites work: Q4198056
cites work: Q4852904
cites work: Bounded queries in recursion theory
cites work: Using self-reducibilities to characterize polynomial time
cites work: Q4251058
cites work: Optimal advice
cites work: Theory of semi-feasible algorithms
cites work: Q4281521
cites work: Q3957950
cites work: On self-reducibility and weak P-selectivity
cites work: The complexity of optimization problems
cites work: A proof of Beigel's cardinality conjecture
cites work: Q3329452
cites work: The global power of additional queries to \(p\)-random oracles
cites work: Polynomial-Time Membership Comparable Sets
cites work: A cardinality version of Beigel's nonspeedup theorem
cites work: Q5573961
cites work: A low and a high hierarchy within NP
cites work: Probabilistic complexity classes and lowness
cites work: Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
cites work: On membership comparable sets
cites work: Recursively enumerable sets and degrees
cites work: The polynomial-time hierarchy
cites work: Q4131648
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
cites work: Relativized circuit complexity
cites work: Complete sets and the polynomial-time hierarchy
cites work: Some consequences of non-uniform conditions on uniform classes
full work available at URL: s0890-5401(03)00091-9
OpenAlex ID: W1986637231
description: scientific article; zbMATH DE number 2056454