Кібернетика і Системний Аналіз
Міжнародний Науково-Теоретичний Журнал
Анотація.
Розглянуто гіпотезу Блера (Blair) про обчислювальну складність задачі, пов’язаної з оптимальними розв’язками так званих близьких задач про рюкзак. Гіпотезу доведено для узагальнено близьких задач про рюкзак.
Ключові слова: складність аналізу стійкості, NP- (DP-) важкі задачі.
Михайлюк Виктор Алексеевич, докторант Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
e-mail: mikhailyukvictor2@gmail.com
Лищук Наталия Викторовна, аспирантка Волынского национального университета имени Леси Украинки, Луцк,
e-mail: Lnatalkav@mail.ru
