Lower bounds for constant-depth circuits in the presence of help bits

DOI10.1016/0020-0190(90)90101-3zbMath0704.68040OpenAlexW2092653296MaRDI QIDQ917289

Jin-Yi Cai

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90101-3

zbMATH Keywords

constant-depth circuitsrandom oracle separation for PH and PSPACE

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

SEPARATING AUXILIARY ARITY HIERARCHY OF FIRST-ORDER INCREMENTAL EVALUATION SYSTEMS USING (3K+1)-ary INPUT RELATIONS ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ The value of help bits in randomized and average-case complexity ⋮ Arity bounds in first-order incremental evaluation and definition of polynomial time database queries

Cites Work

• Unnamed Item
• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Polynomial terse sets
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• The polynomial-time hierarchy
• Parity, circuits, and the polynomial-time hierarchy
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The Boolean Hierarchy II: Applications
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

This page was built for publication: Lower bounds for constant-depth circuits in the presence of help bits