The fault tolerance of NP-hard problems

DOI10.1016/J.IC.2010.11.012MaRDI QIDQ553311zbMATH OpenOpenAlexFDO

Authors Christian Glaßer, Aduri Pavan, Stephen Travers

Publication date 27 July 2011

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2010.11.012

zbMATH Keywords

btt-complete setsfaulty dataleft-set techniquem-complete setsNP-hard setsp-closenessself-correctable

Mathematics Subject Classification ID

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

Recommendations

• The Fault Tolerance of NP-Hard Problems
• On Worst‐Case to Average‐Case Reductions for NP Problems
• A note on closeness between \(NP\)-hard sets and \(C_= P\)
• Approximable sets
• On coherence, random-self-reducibility, and self-correction

Cites work

• A comparison of polynomial time reducibilities
• A Note on Sparse Complete Sets
• 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 Q553311)