DAA - класс P и NP
В компьютерных науках решается множество задач, цель которых - максимизировать или минимизировать некоторые значения, тогда как в других задачах мы пытаемся найти решение, есть ли решение. Следовательно, проблемы можно разделить на следующие категории:
Проблема оптимизации
Задачи оптимизации - это проблемы, цель которых - максимизировать или минимизировать некоторые значения. Например,
Нахождение минимального количества цветов, необходимого для раскрашивания данного графика.
Нахождение кратчайшего пути между двумя вершинами в графе.
Решение проблемы
Есть много проблем, на которые можно ответить "да" или "нет". Эти типы проблем известны как decision problems. Например,
Можно ли раскрасить данный граф только в 4 цвета.
Нахождение гамильтонова цикла в графе не является проблемой решения, тогда как проверка того, является ли граф гамильтоновым или нет, является проблемой решения.
Что такое язык?
У каждой проблемы решения может быть только два ответа: да или нет. Следовательно, проблема принятия решения может принадлежать языку, если он дает ответ «да» на конкретный ввод. Язык - это совокупность входов, для которых ответ положительный. Большинство алгоритмов, обсуждаемых в предыдущих главах, являютсяpolynomial time algorithms.
Для размера ввода n, если наихудшая временная сложность алгоритма равна O(nk), где k - константа, алгоритм представляет собой алгоритм с полиномиальным временем.
Такие алгоритмы, как умножение цепочки матриц, кратчайший путь от одного источника, кратчайший путь для всех пар, минимальное связующее дерево и т. Д., Выполняются за полиномиальное время. Однако существует множество проблем, таких как коммивояжер, оптимальная раскраска графа, гамильтоновы циклы, поиск самого длинного пути в графе и выполнение булевой формулы, для которых не известны алгоритмы с полиномиальным временем. Эти проблемы относятся к интересному классу задач, называемыхNP-Complete проблемы, статус которых неизвестен.
В этом контексте мы можем классифицировать проблемы следующим образом:
P-класс
Класс P состоит из тех задач, которые решаются за полиномиальное время, т.е. эти задачи могут быть решены за время. O(nk) в худшем случае, когда k постоянно.
Эти проблемы называются tractable, а другие называются intractable or superpolynomial.
Формально алгоритм является алгоритмом полиномиального времени, если существует полиномиальный алгоритм p(n) так что алгоритм может решить любой экземпляр размера n вовремя O(p(n)).
Проблема, требующая Ω(n50) время, чтобы решить, по сути, трудно решить для больших n. Самый известный алгоритм полиномиального времени работает во времениO(nk) за довольно низкую стоимость k.
Преимущества рассмотрения класса алгоритмов с полиномиальным временем заключаются в том, что все разумные deterministic single processor model of computation могут быть смоделированы друг на друга не более чем с полиномиальным медленным d
NP-Класс
Класс NP состоит из тех задач, которые проверяются за полиномиальное время. NP - это класс задач решения, для которых легко проверить правильность заявленного ответа с помощью небольшой дополнительной информации. Следовательно, мы не ищем способа найти решение, а только для того, чтобы убедиться, что предполагаемое решение действительно верно.
Каждая проблема этого класса может быть решена за экспоненциальное время с помощью исчерпывающего поиска.
P против NP
Каждая проблема решения, которая решается детерминированным алгоритмом с полиномиальным временем, также разрешима с помощью недетерминированного алгоритма с полиномиальным временем.
Все проблемы в P могут быть решены с помощью алгоритмов с полиномиальным временем, тогда как все проблемы в NP - P трудноразрешимы.
Неизвестно, были ли P = NP. Однако в NP известно множество задач, которые принадлежат P, то можно доказать, что P = NP.
Если P ≠ NP, в NP есть задачи, которых нет ни в P, ни в NP-Complete.
Проблема принадлежит классу Pесли легко найти решение проблемы. Проблема принадлежитNP, если легко найти решение, которое, возможно, было очень утомительным.