Robustness of PSPACE-complete sets

DOI10.1016/J.IPL.2007.02.018MaRDI QIDQ2379952zbMATH OpenOpenAlexFDO

Authors Aduri 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

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

Recommendations

• Splittings, Robustness, and Structure of Complete Sets
• scientific article; zbMATH DE number 512826
• Robustness against Power is PSpace-complete
• The robust set problem: parameterized complexity and approximation
• Completeness results for parameterized space classes
• scientific article; zbMATH DE number 1542828
• scientific article; zbMATH DE number 1419228
• scientific article; zbMATH DE number 4081538
• Strong and robustly strong polynomial-time reducibilities to sparse sets
• Complete sets and closeness to complexity classes

Cites work

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

Cited in

(2)

• The PSPACE-Completeness of Black-White Pebbling
• scientific article; zbMATH DE number 1678398 (Why is no real title available?)

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

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