Length-increasing reductions for PSPACE-completeness

DOI10.1007/978-3-642-40313-2_48MaRDI QIDQ2849941zbMATH OpenOpenAlexFDO

Authors John M. Hitchcock, Aduri Pavan

Publication date 20 September 2013

Published in Mathematical Foundations of Computer Science 2013 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-40313-2_48

zbMATH Keywords

computational complexitycompletenessPSPACElength-increasing reductions

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)

Recommendations

• On polynomial-time Turing and many-one completeness in PSPACE
• Completeness and weak completeness under polynomial-size circuits
• Isomorphisms and 1-L reductions
• Mathematical Foundations of Computer Science 2005
• scientific article; zbMATH DE number 3984574

Cited in

(1)

• On polynomial-time Turing and many-one completeness in PSPACE

This page was built for publication: Length-increasing reductions for PSPACE-completeness

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