The fault tolerance of NP-hard problems

作者:Glasser Christian*; Pavan A; Travers Stephen
来源:Information and Computation, 2011, 209(3): 443-455.
DOI:10.1016/j.ic.2010.11.012

摘要

We study the effects of faulty data on NP-hard sets. We consider hard sets for several polynomial time reductions, add corrupt data and then analyze whether the resulting sets are still hard for NP. We explain that our results are related to a weakened deterministic variant of the notion of program self-correction by Blum, Luby, and Rubinfeld. Among other results, we use the Left-Set technique to prove that m-complete sets for NP are nonadaptively weakly deterministically self-correctable while btt-complete sets for NP are weakly deterministically self-correctable. Our results can also be applied to the study of Yesha's p-closeness. In particular, we strengthen a result by Ogiwara and Fu.

  • 出版日期2011-3

全文