Robustness of PSPACE-complete sets

DOI10.1016/J.IPL.2007.02.018zbMath1187.68252OpenAlexW2152323610MaRDI QIDQ2379952

A. Pavan, Fengming Wang

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.02.018

zbMATH Keywords

computational complexityrobustnesscomplete setsPSPACEP-selective sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Exponential-time and subexponential-time sets
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets
• Properties of NP‐Complete Sets
• PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Splittings, Robustness, and Structure of Complete Sets
• Complete sets and closeness to complexity classes

This page was built for publication: Robustness of PSPACE-complete sets