Редактирование: Методы Оптимизации, Теормин
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 41 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 140: | Строка 140: | ||
Теорема. Если NP не совпадает с P, то ни для какой сильно-NPC задачи не существует псевдополиномиального решения. | Теорема. Если NP не совпадает с P, то ни для какой сильно-NPC задачи не существует псевдополиномиального решения. | ||
- | === Определение | + | === Определение <math>\varepsilon</math>-приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС). Связь между существованием ПППС и псевдополиномиальностью === |
'' Методичка, стр. 22-24 '' | '' Методичка, стр. 22-24 '' | ||
Строка 148: | Строка 148: | ||
* <math>\max</math> вообще говоря вполне может быть заменён на <math>\min</math> | * <math>\max</math> вообще говоря вполне может быть заменён на <math>\min</math> | ||
- | Алгоритм <math>A</math> называется '''приближённым алгоритмом''' решения массовой задачи <math>\Pi</math>, если для любой задачи <math>I \in \Pi</math> он находит точку <math>z_A(I) \in S_\Pi(I)</math>, лежащую в области допустимых значений, принимаемую за приближённое решение | + | Алгоритм <math>A</math> называется '''приближённым алгоритмом''' решения массовой задачи <math>\Pi</math>, если для любой задачи <math>I \in \Pi</math> он находит точку <math>z_A(I) \in S_\Pi(I)</math>, лежащую в области допустимых значений, принимаемую за приближённое решение |
- | ''Утверждение'' | + | ''Утверждение'' Если <math>\mathrm{P} \neq \mathrm{NP}</math>, то ни для какой константы <math>C > 0</math> не существует полиномиального приближённого алгоритма решения задачи о рюкзаке с оценкой <math>| \mathrm{Opt}(I) - A(I) | \leqslant C</math> |
- | Приближённый алгоритм <math>A</math> решения массовой задачи <math>\Pi</math> называется ''' <math>\varepsilon</math>-приближённым алгоритмом ''' решения задачи, если <math>\forall I \in \Pi : ~ \left| \frac{\mathrm{Opt}_\Pi(I) - A(I)}{\mathrm{Opt}_\Pi(I)} \right| \leqslant \varepsilon</math> | + | Приближённый алгоритм <math>A</math> решения массовой задачи <math>\Pi</math> называется ''' <math>\varepsilon</math>-приближённым алгоритмом ''' решения задачи, если <math>\forall I \in \Pi : ~ \left| \frac{\mathrm{Opt}_\Pi(I) - A(I)}{\mathrm{Opt}_\Pi(I)} \right| \leqslant \varepsilon</math> |
=== Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания === | === Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания === |