The fault tolerance of NP-hard problems

DOI10.1016/j.ic.2010.11.012zbMath1234.68136OpenAlexW2654659232MaRDI QIDQ553311

Stephen Travers, Christian Glaßer, A. Pavan

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)

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

This page was built for publication: The fault tolerance of NP-hard problems