The Fault Tolerance of NP-Hard Problems

DOI10.1007/978-3-642-00982-2_32MaRDI QIDQ3618596zbMATHOpenAlexFDO

Authors Christian Glaßer, Aduri 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)

Recommendations

• The fault tolerance of NP-hard problems
• Fault-tolerance and complexity (extended abstract)
• scientific article; zbMATH DE number 913541
• scientific article; zbMATH DE number 1775419
• An Approximation Formula for a Class of Fault-Tolerant Computers
• Algorithmic Fault Tolerance Using the Lanczos Method
• scientific article
• The Complexity of Fault Detection Problems for Combinational Logic Circuits
• Fault-tolerant Computation in the Full Information Model
• Troubleshooting: NP-hardness and solution methods

Cites work

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

Cited in

(1)

• The fault tolerance of NP-hard problems

This page was built for publication: The Fault Tolerance of NP-Hard Problems

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