Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации
Показано, що ZPP-, RP-ймовірнісних поліноміальних процедури постоптимального аналізу для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної в одній позиції матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і ZPP ≠ NP (RP ≠...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/84154 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 3-10. — Бібліогр.: 10 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84154 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-841542015-07-04T03:01:33Z Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации Михайлюк, В.А. Кибернетика Показано, що ZPP-, RP-ймовірнісних поліноміальних процедури постоптимального аналізу для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної в одній позиції матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і ZPP ≠ NP (RP ≠ NP). Подібний результат маємо для задачі про ранець. It is shown that a ZPP-, RP-probabilistic polynomial procedures of postoptimality analysis for finding the optimal solution of a set cover problem that differs from the original problem in one position of matrix of constraints do not exist if the optimal solution of the original problem is known and if ZPP ≠ NP (RP ≠ NP) A similar result holds for the knapsack problem. 2012 Article Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 3-10. — Бібліогр.: 10 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84154 519.854 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Михайлюк, В.А. Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации Кибернетика и системный анализ |
| description |
Показано, що ZPP-, RP-ймовірнісних поліноміальних процедури постоптимального аналізу для визначення оптимального розв’язку задачі про покриття множинами, яка відрізняється від вихідної в одній позиції матриці обмежень, не існує, якщо виходити з оптимального розв’язку вихідної задачі і ZPP ≠ NP (RP ≠ NP). Подібний результат маємо для задачі про ранець. |
| format |
Article |
| author |
Михайлюк, В.А. |
| author_facet |
Михайлюк, В.А. |
| author_sort |
Михайлюк, В.А. |
| title |
Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации |
| title_short |
Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации |
| title_full |
Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации |
| title_fullStr |
Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации |
| title_full_unstemmed |
Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации |
| title_sort |
подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84154 |
| citation_txt |
Подход к оценке сложности вероятностных процедур постоптимального анализа дискретных задач оптимизации / В.А. Михайлюк // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 3-10. — Бібліогр.: 10 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT mihajlûkva podhodkocenkesložnostiveroâtnostnyhprocedurpostoptimalʹnogoanalizadiskretnyhzadačoptimizacii |
| first_indexed |
2023-10-18T19:28:19Z |
| last_indexed |
2023-10-18T19:28:19Z |
| _version_ |
1796147049756884992 |