Alternative definition of the strong NP-completeness
https://doi.org/10.29235/1561-2430-2024-60-4-303-308
Abstract
The paper explains the shortcomings of the existing definition of the strong NP-completeness. An alternative definition is proposed, that preserves all existing results on proving the strong NP-completeness of decision problems. Besides, the definition of NP-completeness and the alternative definition of the strong NP-completeness have the same structure.
About the Author
Ya. M. Shafransky
United Institute of Informatics Problems of the National Academy of Sciences of Belarus
Belarus
Yakov M. Shafransky – Ph. D. (Physics and Mathematics), Associate Professor, Leading Researcher of the Laboratory of Mathematical Cybernetics
6, Surganov Str., Minsk, 220072
References
1. Garey M. R., Johnson D. S. “Strong” NP-completeness results: motivation, examples, and implications. Journal of the Association for Computing Machinery, 1978, vol. 25, no. 3, pp. 499-508. https://doi.org/10.1145/322077.322090
2. Garey M. R., Johnson D. S. Computers and Intractability. A Guide to the Theory of NP-completeness. New York, W. H. Freeman and Company, 1979. 348 p.
3. Webster S. Note on “Parallel Machine Scheduling with Batch Setup Times”. Operations Research, 1998, vol. 46, no. 3, p. 423. https://doi.org/10.1287/opre.46.3.423
4. Shafransky Y. M. On some contradictions in theory of computational complexity. Third Workshop on Models and Algorithms for Planning and Scheduling. Cambridge, 1997, p. 42.
Views:
180
Email this article 