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

DOI10.1137/050642228MaRDI QIDQ3446808zbMATH OpenOpenAlexFDO

Authors 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

polynomial-time hierarchyrandomized algorithmssatisfiabilitytime-space lower bounds

Mathematics Subject Classification ID

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

Recommendations

• Automata, Languages and Programming
• Time-space lower bounds for satisfiability
• Inductive time-space lower bounds for SAT and related problems
• Time-space lower bounds for satisfiability
• Automata, Languages and Programming

Cited in

(15)

• Simultaneous (poly-time, log-space) lower bounds
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• Almost-everywhere complexity hierarchies for nondeterministic time
• Local expanders
• Inductive time-space lower bounds for SAT and related problems
• Lower space bounds for randomized computation
• Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines
• Limits on alternation trading proofs for time-space lower bounds
• Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
• Typically-correct derandomization for small time and space
• scientific article; zbMATH DE number 7250155 (Why is no real title available?)
• Automata, Languages and Programming
• Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\)
• On quasilinear-time complexity theory
• Time-space lower bounds for simulating proof systems with quantum and randomized verifiers

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3446808)