Robustness of PSPACE-complete sets
DOI10.1016/J.IPL.2007.02.018zbMATH Open1187.68252OpenAlexW2152323610MaRDI QIDQ2379952FDOQ2379952
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
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
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)
Cites Work
- 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
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Complete sets and closeness to complexity classes
- PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS
- Exponential-time and subexponential-time sets
- A Post's program for complexity theory.
- Properties of NP‐Complete Sets
- Splittings, Robustness, and Structure of Complete Sets
Cited In (2)
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)
