vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2024-60-4-303-308vestifm-810Research ArticleМАТЕМАТИКАMATHEMATICSАльтернативное определение NP-полноты в сильном смыслеAlternative definition of the strong NP-completenessШафранскийЯ. М.ShafranskyYa. M.

Шафранский Яков Михайлович – кандидат физико-математических наук, доцент, ведущий научный сотрудник лаборатории математической кибернетики

ул. Сурганова, 6, 220072, Минск

Yakov M. Shafransky – Ph. D. (Physics and Mathematics), Associate Professor, Leading Researcher of the Laboratory of Mathematical Cybernetics

6, Surganov Str., Minsk, 220072

shafr-04@yandex.byОбъединенный институт проблем информатики Национальной академии наук БеларусиUnited Institute of Informatics Problems of the National Academy of Sciences of Belarus202408012025604303308Copyright © Шафранский Я.М., 20252025Шафранский Я.М.Shafransky Y.M.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/810

Объясняются недостатки существующего определения NP-полноты в сильном смысле. Пред лагается альтернативное определение, сохраняющее все существующие результаты по доказательству NP-полноты в сильном смысле задач распознавания.

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. 

задача распознаванияпсевдополиномиальный алгоритмкласс NPNP-полнотаNP-полнота в сильном смыслеdecision problempseudo-polynomial algorithmclass NPNP-completenessstrong NP-completenessReferencesGarey, M. R. “Strong” NP-completeness results: motivation, examples, and implications / M. R. Garey, D. S. Johnson // J. Ass. Comput. Machinery. – 1978. – Vol. 25, № 3. – P. 499–508. https://doi.org/10.1145/322077.322090Garey 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.322090Garey, M. R. Computers and Intractability. A Guide to the Theory of NP-completeness / M. R. Garey, D. S. Johnson. – New York: W. H. Freeman and Company, 1979. – 348 p.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.Webster, S. Note on “Parallel Machine Scheduling with Batch Setup Times” / S. Webster // Oper. Res. – 1998. – Vol. 46, № 3. – P. 423. https://doi.org/10.1287/opre.46.3.423Webster 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.423Shafransky, Y. M. On some contradictions in theory of computational complexity / Y. M. Shafransky // Third Workshop on Models and Algorithms for Planning and Scheduling. – Cambridge, 1997. – P. 42.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.

The authors declare that there are no conflicts of interest present.