The Fault Tolerance of NP-Hard Problems

DOI10.1007/978-3-642-00982-2_32zbMath1234.68135OpenAlexW1513273197MaRDI QIDQ3618596

Christian Glaßer, A. Pavan, Stephen Travers

Publication date: 2 April 2009

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• On sparse hard sets for counting classes
• A comparison of polynomial time reducibilities
• Self-testing/correcting with applications to numerical problems
• A Note on Sparse Complete Sets
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• On lower bounds of the closeness between complexity classes
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Complete sets and closeness to complexity classes
• Redundancy in Complete Sets