On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results

DOI10.1007/3-540-45071-8_22zbMATH Open1276.68080OpenAlexW1481279691MaRDI QIDQ3082928

Jin-Yi Cai, Osamu Watanabe

Publication date: 18 March 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-45071-8_22

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)

Unnamed Item ⋮ Unnamed Item

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