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