Lower bounds for constant-depth circuits in the presence of help bits
type: Item
instance of: scholarly article
title: Lower bounds for constant-depth circuits in the presence of help bits
zbMATH Open document ID: 0704.68040
DOI: 10.1016/0020-0190(90)90101-3
published in: Information Processing Letters
publication date: 1990-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 4155878
zbMATH Keywords: constant-depth circuits
zbMATH Keywords: random oracle separation for PH and PSPACE
author: Jin-Yi Cai
MaRDI profile type: Publication
full work available at URL: 0020-0190(90)90101-3
OpenAlex ID: W2092653296
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Polynomial terse sets
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
cites work: The Boolean Hierarchy II: Applications
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
cites work: Q5557960
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: Q4035672
cites work: The polynomial-time hierarchy
Recommended article: Q3321475
Recommended article: Lower bounds and separations for constant depth multilinear circuits
Recommended article: Q4703651
Recommended article: Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
Recommended article: On the Hardness against Constant-Depth Linear-Size Circuits
Recommended article: ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS
Recommended article: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
Recommended article: Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity
Recommended article: Exponential lower bound for bounded depth circuits with few threshold gates
Recommended article: On Lower Bounds for Constant Width Arithmetic Circuits
description: scientific article; zbMATH DE number 4155878