Редактирование: Методы Оптимизации, Теормин
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 41 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 55: | Строка 55: | ||
* задачи, для которых длина записи выхода превышает любой наперед заданный полином от длины входа | * задачи, для которых длина записи выхода превышает любой наперед заданный полином от длины входа | ||
** найти все маршруты в задаче коммивояжёра | ** найти все маршруты в задаче коммивояжёра | ||
- | * ∀А, решающего П с кодировкой e, ∀p(·) ∃I ∈ П: <math>t_A(e(I)) > p(|e(I)|)</math> | ||
- | |||
'''Класс недетерминированно полиномиальных задач (NP)''' -- это такие задачи, для которых существует алгоритм решения на недерменированной машине Тьюринга: | '''Класс недетерминированно полиномиальных задач (NP)''' -- это такие задачи, для которых существует алгоритм решения на недерменированной машине Тьюринга: |