Редактирование: Методы Оптимизации, Теормин
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 40 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 84: | Строка 84: | ||
* пример такой задачи -- это задача определения простоты числа. | * пример такой задачи -- это задача определения простоты числа. | ||
* <math>P \subseteq \text{NP} \cap \text{co-NP}</math> | * <math>P \subseteq \text{NP} \cap \text{co-NP}</math> | ||
- | |||
- | Массовая задача <math>\Pi'</math> с кодировкой <math>e'</math> ''' полиномиально сводится ''' к задаче <math>\Pi</math> с кодировкой <math>e</math>, если любая индивидуальная задача <math>I' \in \Pi'</math> может быть сведена за полиномиальное от её длины время к некоторой задаче <math>I \in \Pi</math> с сохранением ответа. | ||
- | |||
- | Массовая задача <math>\Pi</math> называется '''NP-полной (универсальной)''', если | ||
- | * принадлежит классу NP: <math>\Pi \in \text{NP}</math> | ||
- | * любая задача из NP полиномиально сводится к <math>\Pi</math>: <math>\forall \Pi' \in \text{NP} ~~~ \Pi' \propto \Pi</math> | ||
- | |||
- | Класс '''NPC (NP-complete)''' -- множество всех NP-полных задач. | ||
=== Критерий NP-полноты. Д-во NP-полноты задачи ЦЛН === | === Критерий NP-полноты. Д-во NP-полноты задачи ЦЛН === |