Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines

DOI10.1137/050642228zbMath1120.68055OpenAlexW2109520329MaRDI QIDQ3446808

Scott Diehl, Dieter van Melkebeek

Publication date: 26 June 2007

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

Full work available at URL: https://doi.org/10.1137/050642228

zbMATH Keywords

satisfiabilityrandomized algorithmspolynomial-time hierarchytime-space lower bounds

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Local expanders ⋮ Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\) ⋮ Limits on alternation trading proofs for time-space lower bounds ⋮ Unnamed Item ⋮ Typically-correct derandomization for small time and space

This page was built for publication: Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines