Начало
Учебные материалы
Классы сложности задач. Методы решения трудных задач
Классы сложности задач Сравнение методов решения трудных задач Метод поиска с возвратом Метод ветвей и границ
Классы сложности задач
время, если его временная эффективность в наихудшем случае принадлежит
классу `O(P(n))`, где `P(n)` —
полином от размера входных данных n.
Так как мы используем запись с большим "О", задачи, решаемые
за логарифмическое время, включаются в `O(P(n))`.
Задачу, которая может быть решена за полиномиальное время, будем называть
*легкой*, а задачу, которая не может быть решена за полиномиальное
время, — *трудной*.
--
* Мы не можем решить произвольные экземпляры трудных задач за реальное время,
за исключением только очень малых экземпляров.
* Существует очень мало используемых на практике полиномиальных алгоритмов со степенью полинома
больше трех. Кроме того, полиномы, ограничивающие время работы алгоритма,
обычно не содержат очень больших коэффициентов.
* Полиномиальные функции обладают многими удобными свойствами; в частности, как сумма, так
и композиция двух полиномов всегда остаются полиномами.
* Из теории вычислительной сложности следует, что трудность остается одной и той же для всех
основных моделей вычислений и разумных схем кодирования входной
информации рассматриваемой задачи.
--
*Задачи принятия решения* (ЗПР) представляют собой задачи, ответ на которые —
"да" либо "нет".
Класс `P` представляет собой класс задач принятия решения,
которые могут быть решены (детерминистическим) алгоритмом за полиномиальное
время. Этот класс задач называется полиномиальным.
--
Ограничение класса `P` только задачами принятия решения можно объяснить
следующими причинами.
1. Разумно исключить задачи, не разрешимые
за полиномиальное время из-за экспоненциально большого размера выходных
данных (например, генерация
всех подмножеств данного множества).
2. Многие важные задачи, не являющиеся
задачами принятия решения в своей естественной формулировке, могут быть приведены
к задаче принятия решения, которые проще изучить.
Например, вместо выяснения, какое наименьшее количество цветов надо для раскраски вершин графа,
так, чтобы никакие две смежные вершины не были одного цвета, мы можем
выяснять, существует ли такая раскраска вершин графа не более чем `m` цветами
при `m = 1,2,...`.
--
Некоторые задачи принятия решения не могут быть решены вообще, никаким
алгоритмом. Такие задачи называются *неразрешимыми*.
Например, задача останова: для данной компьютерной программы
и входных данных определить, завершится ли выполнение программы или она
будет выполняться бесконечно.
Существуют задачи разрешимые, но трудные.
Но для многих важных задач не был найден
алгоритм с полиномиальным временем работы, но и не доказана невозможность его
существования. Например, задача коммивояжера, задача о рюкзаке, упаковка корзин, раскраска графа,
целочисленное линейное программирование.
--
Задача обхода всех ребер по одному разу
(эйлеров цикл) может быть решена за `O(n^2)` в отличие от похожей задачи о цикле, обходящем
по одному разу все вершины (гамильтонов цикл), для которой не найдено полиномиальное решение.
При том, что решение задач может быть вычислительно
сложным, проверка предложенного решения обычно достаточно проста и может
быть выполнена за полиномиальное время.
--
*Недетерминистическим алгоритмом* называется двухэтапная процедура, которая получает в качестве входа
экземпляр `I` задачи принятия решения и делает следующее.
1. Недетерминистический этап ("угадывания"): генерируется произвольная
строка `S`, которая может рассматриваться как кандидат в решение данной задачи `I`.
2. Детерминистический этап ("проверки"): детерминистический алгоритм
получает `I` и `S` в качестве входных данных и выдает "да", если `S` представляет собой
решение экземпляра `I`. (Если `S` не является решением `I`, алгоритм либо
возвращает "нет", либо может вообще не завершить работу.)
--
Недетерминистический алгоритм является
*недетерминистическим полиномиальным*, если временная
эффективность этапа проверки полиномиальная.
Класс `NP` — это класс задач принятия решения, которые могут
быть решены недетерминистическим полиномиальным алгоритмом. Этот класс
задач называется *недетерминистическим полиномиальным*.
Большинство задач принятия решения принадлежат классу `NP`. Прежде всего
этот класс включает все задачи класса `P`: `P sube NP`.
С другой стороны, задача останова не входит в класс `NP`.
--
Наиболее важный открытый вопрос теоретической
информатики: является ли класс `P` истинным подмножеством `NP` или на самом деле
оба эти класса совпадают?
Некоторые известные задачи принятия решения являются `NP`-полными.
`NP`-*полная* задача — это задача класса `NP`, которая
так же сложна, как и любая другая задача этого класса, поскольку по определению
любая другая задача класса `NP` может быть приведена к ней за полиномиальное
время.
Из определения `NP`-полноты следует, что если будет найден
детерминистический алгоритм решения одной из `NP`-полных задач, то все задачи
в NP могут быть решены за полиномиальное время при помощи
детерминистического алгоритма, следовательно, `P = NP`.
--
Первой найденной в 1971г. задачей из класса `NP`-полных стала задача CNF-выполнимости,
в которой спрашивается, можно ли назначить переменным
в булевом выражении значения true и false так, чтобы результат вычисления
всего выражения был равен true.
С того времени были найдены сотни других примеров `NP`-полных задач.
Известно, однако, что если `P!=NP`, то должны существовать `NP`-задачи, которые не
являются ни `P`-задачами, ни `NP`-полными задачами.
Много лет ведущим кандидатом в примеры такой задачи была задача
определения того, является ли заданное число простым или составным, но в 2002 был открыт
детерминистический полиномиальный алгоритм для проверки простоты числа.
--
Предположим, мы определили, что число составное, можно ли сформулировать
задачу разложения числа на множители как ЗПР? Например, можно задавать вопрос: "имеет ли число `N` делитель в интервале `[2, B]`?". Перебирая `B` бинарным поиском от 2 до `sqrt N`, можно найти наименьшее значение `p`, дающее ответ "да" -- это и будет первым из множителей. Далее ищем делитель для `N//p` и так далее.
Несмотря на похожесть задач проверки числа на простоту и проверки наличия делителя в интервале `[2, B]`, первая задача относится к классу `P`, а вторая -- к классу `NP` (проверить, что число является делителем можно за `O(n^2)`, где `n=|~log N~|` -- количество цифр в числе). Если бы существовал полиномиальный алгоритм `O(n^k)` для второй задачи, то можно было бы выполнить разложение на множители также за полиномиальное время: количество делителей не превышает `log_2 N`, каждый из них может быть найден за `O(n^k log N)=O(n^{k+1})`, таким образом итоговый алгоритм имел бы оценку `O(n^{k+2})`. Задача разложения на множители является трудной (см. упражнения), может быть сформулирована как `NP`, но не является `NP`-полной (так как невозможно привести другие `NP`-полные задачи к разложению на множители).
--
На сегодняшний день знание того, что задача является `NP`-полной, имеет важные
практические следствия. Это означает, что, столкнувшись с `NP`-полной задачей, не стоит
устраивать революцию в информатике, разрабатывая полиномиальный алгоритм.
Вместо этого следует сконцентрироваться на нескольких подходах поиска уменьшения сложности
стоящей перед вами задачи.
---
##### Задания для практики
1. Задача может быть решена при помощи алгоритма со временем работы `O(n^{log_2 n})`. Какие из следующих утверждений истинны?\
а) Задача легкая.\
б) Задача трудная.\
в) Ни одно из приведенных утверждений.
2. Рассмотрим следующий алгоритм грубой силы для решения задачи о составных числах: последовательно проверяем все целые числа от 2 до `|__n//2__|` в качестве возможных делителей `n`. Если на одно из них `n` делится нацело, возвращаем ответ "да" (т.е. число составное), если не делится ни на одно - возвращаем ответ "нет". Почему этот алгоритм не делает задачу принадлежащей классу `P`?
