On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy

DOI10.1137/S0097539703422716zbMath1105.68041MaRDI QIDQ4651502

Osamu Watanabe, Jin-Yi Cai

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

computational complexitycircuit complexityNisan-Wigderson generatorstringent relativizationSwitching Lemma

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

On the Limit of Some Algorithmic Approach to Circuit Lower Bounds ⋮ Parity, circuits, and the polynomial-time hierarchy

This page was built for publication: On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy