×

The fault tolerance of NP-hard problems. (English) Zbl 1234.68136

Summary: 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.

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blum, M.; Luby, M.; Rubinfeld, R., Self-testing/correcting with applications to numerical problems, J. Comput. System Sci., 47, 3, 549-595 (1993) · Zbl 0795.68131
[2] Yesha, Y., On certain polynomial-time truth-table reducibilities of complete sets to sparse sets, SIAM J. Comput., 12, 3, 411-425 (1983) · Zbl 0545.03023
[3] M. Ogiwara, On P-closeness of polynomial-time hard sets, unpublished manuscript, 1991.; M. Ogiwara, On P-closeness of polynomial-time hard sets, unpublished manuscript, 1991.
[4] Fu, B., On lower bounds of the closeness between complexity classes, Math. Systems Theory, 26, 2, 187-202 (1993) · Zbl 0771.68050
[5] Ladner, R. E.; Lynch, N. A.; Selman, A. L., A comparison of polynomial time reducibilities, Theor. Comput. Sci., 1, 103-123 (1975) · Zbl 0321.68039
[6] Berman, L.; Hartmanis, J., On isomorphism and density of NP and other complete sets, SIAM J. Comput., 6, 305-322 (1977) · Zbl 0356.68059
[7] Glaßer, C.; Pavan, A.; Selman, A. L.; Zhang, L., Redundancy in complete sets, (Proceedings 23nd Symposium on Theoretical Aspects of Computer Science. Proceedings 23nd Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 3884 (2006), Springer), 444-454 · Zbl 1136.68027
[8] Ogiwara, M.; Watanabe, O., On polynomial-time bounded truth-table reducibility of NP sets to sparse sets, SIAM J. Comput., 20, 3, 471-483 (1991) · Zbl 0741.68049
[9] Fortune, S., A note on sparse complete sets, SIAM J. Comput., 8, 3, 431-433 (1979) · Zbl 0415.68006
[10] Ogiwara, M.; Lozano, A., On sparse hard sets for counting classes, Theor. Comput. Sci., 112, 2, 255-275 (1993) · Zbl 0780.68043
[11] Schöning, U., Complete sets and closeness to complexity classes, Math. Systems Theory, 19, 1, 29-41 (1986) · Zbl 0617.68047
[12] L.A. Hemachandra, M. Ogiwara, O. Watanabe, How hard are sparse sets?, in: Structure in Complexity Theory Conference, 1992, pp. 222-238.; L.A. Hemachandra, M. Ogiwara, O. Watanabe, How hard are sparse sets?, in: Structure in Complexity Theory Conference, 1992, pp. 222-238.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.