Я предполагаю, что вы ищете интуитивные определения, так как технические определения требуют некоторого времени для понимания. Прежде всего, давайте вспомним предварительную необходимую концепцию, чтобы понять эти определения.
- Проблема с решением : Проблема с ответом да или нет .
Теперь давайте определим эти классы сложности .
P
P - класс сложности, представляющий совокупность всех задач решения, которые могут быть решены за полиномиальное время .
То есть, учитывая случай проблемы, ответ да или нет может быть решен за полиномиальное время.
* * Пример тысячи двадцать-шести * 1 028 *
Для связного графа G, можно ли закрасить его вершины двумя цветами, чтобы ни одно ребро не было монохроматическим?
Алгоритм: начните с произвольной вершины, закрасьте ее красным и все его соседи синим и продолжайте. Остановитесь, когда у вас кончатся вершины или вы вынуждены сделать ребро, чтобы обе его конечные точки были одного цвета.
NP
NP - это класс сложности, представляющий набор всех проблем решения, для которых в случаях, когда ответ «да», есть доказательства, которые можно проверить за полиномиальное время.
Это означает, что если кто-то предоставит нам экземпляр проблемы и сертификат (иногда называемый свидетелем) для ответа «да», мы можем проверить его правильность за полиномиальное время.
* ** 1044 тысяча сорок-три * Пример * * тысяча сорок-шести
Целочисленная факторизация в NP. Это проблема того, что для целых чисел n и m существует ли целое число f с 1 < f < m, такое, что f делит n (f - это небольшой коэффициент n)?
Это проблема решения, потому что ответы да или нет. Если кто-то передает нам экземпляр проблемы (поэтому они передают нам целые числа n и m) и целое число f с 1 < f < m, и утверждают, что f является фактором n (сертификат ), мы можем проверить ответ за полиномиальное время , выполнив деление n / f.
NP-Complete
NP-Complete - это класс сложности, представляющий набор всех проблем X в NP, для которых можно уменьшить любую другую проблему NP Y до X за полиномиальное время.
Интуитивно это означает, что мы можем быстро решить Y, если знаем, как быстро X решить. Точно, Y сводится к X, если есть алгоритм полиномиального времени f для преобразования экземпляров y из Y в экземпляры x = f(y) из X за полиномиальное время со свойством, что ответ на y - да, если и только если ответ на f(y) - да.
Пример
3-SAT. Это проблема, в которой нам дано соединение (AND) из трехпозиционных дизъюнкций (OR), операторов вида
(x_v11 OR x_v21 OR x_v31) AND
(x_v12 OR x_v22 OR x_v32) AND
... AND
(x_v1n OR x_v2n OR x_v3n)
, где каждый x_vij является логической переменной или отрицанием переменной из конечного предопределенного списка (x_1, x_2, ... x_n).
Можно показать, что каждая проблема NP может быть уменьшена до 3-SAT . Доказательство этого является техническим и требует использования технического определения NP ( на основе недетерминированных машин Тьюринга ). Это известно как теорема Кука .
Что делает NP-полными задачи важными, так это то, что если для решения одной из них можно найти детерминированный алгоритм за полиномиальное время, то каждая NP-задача разрешима за полиномиальное время (одна проблема, чтобы управлять ими всеми).
NP-трудной
Интуитивно понятно, что это проблемы, которые , по крайней мере, такие же сложные, как проблемы с NP-завершением . Обратите внимание, что NP-сложные проблемы не обязательно должны быть в NP , а они не должны быть проблемами решения .
Точное определение здесь состоит в том, что проблема X является NP-трудной, если существует NP-полная проблема Y, такая, что Y сводится к X за полиномиальное время .
Но поскольку любая NP-полная задача может быть сведена к любой другой NP-полной задаче за полиномиальное время, все NP-полные задачи могут быть сведены к любой NP-сложной задаче за полиномиальное время. Затем, если есть решение одной NP-трудной задачи за полиномиальное время, существует решение всех NP-задач за полиномиальное время.
* +1137 * Пример * +1139 *
Проблема с остановкой - трудная задача NP. Это проблема, при которой программа P и ввод I остановятся? Это проблема решения, но ее нет в NP. Ясно, что любая NP-полная проблема может быть сведена к этой. В качестве другого примера, любая NP-полная проблема является NP-трудной.
Моя любимая NP-полная проблема - это проблема Сапер .
P = NP
Это одна из самых известных проблем в области компьютерных наук и один из самых важных нерешенных вопросов в математических науках. На самом деле, Clay Institute предлагает один миллион долларов для решения этой проблемы (статья Стивена Кука readup на сайте Clay довольно хороша).
Понятно, что P является подмножеством NP. Открытый вопрос состоит в том, имеют ли проблемы NP детерминированные решения за полиномиальное время. Во многом считается, что они этого не делают. Вот выдающаяся недавняя статья о последней (и важности) проблеме P = NP: Состояние проблемы P против NP .
Лучшая книга на эту тему - Компьютеры и Непреодолимость - Гэри и Джонсон.