PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS

DOI10.1142/S0129054191000054zbMath0742.68022OpenAlexW2034955756MaRDI QIDQ3988834

Jin-Yi Cai, Merrick L. Furst

Publication date: 28 June 1992

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054191000054

zbMATH Keywords

branching programsPSPACEserializabilitysafe-storage hierarchy

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria ⋮ Robustness of PSPACE-complete sets ⋮ Autoreducibility, mitoticity, and immunity ⋮ Universally serializable computation ⋮ Nondeterministic stack register machines ⋮ Optimal advice ⋮ Functions computable in polynomial space ⋮ Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes ⋮ Succinct representation, leaf languages, and projection reductions ⋮ Bounding queries in the analytic polynomial-time hierarchy ⋮ SELF-SPECIFYING MACHINES ⋮ Generation problems

This page was built for publication: PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS