Some connections between bounded query classes and non-uniform complexity.

DOI10.1016/S0890-5401(03)00091-9zbMath1058.68056OpenAlexW1986637231MaRDI QIDQ1426008

Richard Beigel, William I. Gasarch, Amihood Amir

Publication date: 14 March 2004

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

Full work available at URL: https://doi.org/10.1016/s0890-5401(03)00091-9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

A relationship between difference hierarchies and relativized polynomial hierarchies, When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one, On the hardness of computing the permanent of random matrices, On computing Boolean connectives of characteristic functions, Time bounded frequency computations, Some connections between bounded query classes and non-uniform complexity., Collapsing and separating completeness notions under average-case and worst-case hypotheses, The 1-versus-2 queries problem revisited, The value of help bits in randomized and average-case complexity, Reductions to sets of low information content, Unnamed Item, Choosing, agreeing, and eliminating in communication complexity, Bounded queries to arbitrary sets, Some structural properties of SAT, One query reducibilities between partial information classes, Optimal series-parallel trade-offs for reducing a function to its own graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal advice
• Some consequences of non-uniform conditions on uniform classes
• A note on enumerative counting
• Lower bounds for constant-depth circuits in the presence of help bits
• A low and a high hierarchy within NP
• On self-reducibility and weak P-selectivity
• Relativized circuit complexity
• Polynomial terse sets
• The complexity of optimization problems
• Bounded queries to SAT and the Boolean hierarchy
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Probabilistic complexity classes and lowness
• Quasi-linear truth-table reductions to \(p\)-selective sets
• Some connections between bounded query classes and non-uniform complexity.
• Terse, superterse, and verbose sets
• Bounded queries in recursion theory
• Enumerative counting is hard
• Quantifying the amount of verboseness
• Approximable sets
• The global power of additional queries to random oracles
• Two queries
• On membership comparable sets
• Using self-reducibilities to characterize polynomial time
• The Global Power of Additional Queries toP-Random Oracles
• The polynomial-time hierarchy and sparse oracles
• PP is as Hard as the Polynomial-Time Hierarchy
• Sparse Sets, Lowness and Highness
• On Sets Truth-Table Reducible to Sparse Sets
• On the Structure of Bounded Queries to Arbitrary NP Sets
• A proof of Beigel's cardinality conjecture
• Recursively enumerable sets and degrees
• A cardinality version of Beigel's nonspeedup theorem
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
• Polynomial-Time Membership Comparable Sets
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• The complexity of ODD_n^A
• Theory of semi-feasible algorithms