Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации

Показано, що поліноміального алгоритму для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної однією позицією матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і умови P ≠ NP. Подібний результат виконується для задачі про...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2010
Автор: Михайлюк, В.А.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2010
Назва видання:Кибернетика и системный анализ
Теми:
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/45150
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Общий подход к оценке сложности постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2010. — № 2. — С. 134-141. — Бібліогр.: 10 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
Опис
Резюме:Показано, що поліноміального алгоритму для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної однією позицією матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і умови P ≠ NP. Подібний результат виконується для задачі про ранець.