Альтернативное определение NP-полноты в сильном смысле
https://doi.org/10.29235/1561-2430-2024-60-4-303-308
Аннотация
Объясняются недостатки существующего определения NP-полноты в сильном смысле. Пред лагается альтернативное определение, сохраняющее все существующие результаты по доказательству NP-полноты в сильном смысле задач распознавания.
Об авторе
Я. М. Шафранский
Объединенный институт проблем информатики Национальной академии наук Беларуси
Беларусь
Беларусь
Шафранский Яков Михайлович – кандидат физико-математических наук, доцент, ведущий научный сотрудник лаборатории математической кибернетики
ул. Сурганова, 6, 220072, Минск
Список литературы
1. Garey, 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.322090
2. Garey, 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.
3. 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.423
4. Shafransky, 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.
Рецензия
Просмотров: 28
Послать статью по эл. почте 