В области компьютерных наук многие проблемы решаются, когда цель состоит в том, чтобы максимизировать или минимизировать некоторые значения, тогда как в других задачах мы пытаемся выяснить, есть ли решение или нет. Следовательно, проблемы могут быть классифицированы следующим образом —
Задача оптимизации
Проблемы оптимизации — те, для которых цель состоит в том, чтобы максимизировать или минимизировать некоторые значения. Например,
-
Нахождение минимального количества цветов, необходимых для раскраски данного графика.
-
Нахождение кратчайшего пути между двумя вершинами графа.
Нахождение минимального количества цветов, необходимых для раскраски данного графика.
Нахождение кратчайшего пути между двумя вершинами графа.
Решение проблемы
Существует много проблем, для которых ответом является «да» или «нет». Эти типы проблем известны как проблемы с решением . Например,
-
Может ли данный график быть окрашен только в 4 цвета.
-
Нахождение гамильтонова цикла в графе не является проблемой решения, тогда как проверка графа является гамильтоновой или нет — это проблема решения.
Может ли данный график быть окрашен только в 4 цвета.
Нахождение гамильтонова цикла в графе не является проблемой решения, тогда как проверка графа является гамильтоновой или нет — это проблема решения.
Что такое язык?
Каждое решение проблемы может иметь только два ответа, да или нет. Следовательно, решение проблемы может принадлежать языку, если он дает ответ «да» для конкретного ввода. Язык — это совокупность входных данных, ответ на которые положительный. Большинство алгоритмов, рассмотренных в предыдущих главах, являются алгоритмами полиномиального времени .
Для входного размера n , если временная сложность алгоритма для наихудшего случая равна O (n k ) , где k — константа, алгоритм — алгоритм полиномиального времени.
Такие алгоритмы, как умножение цепочки матриц, кратчайший путь из одного источника, кратчайший путь для всех пар, минимальное остовное дерево и т. Д., Выполняются за полиномиальное время. Однако существует много проблем, таких как путешествующий продавец, оптимальная раскраска графа, гамильтоновы циклы, поиск самого длинного пути в графе и удовлетворение булевой формулы, для которой не известны алгоритмы полиномиального времени. Эти проблемы относятся к интересному классу задач, называемых задачами NP-Complete , статус которых неизвестен.
В этом контексте мы можем классифицировать проблемы следующим образом:
Р-Класс
Класс P состоит из тех задач, которые разрешимы за полиномиальное время, то есть эти проблемы могут быть решены за время O (n k ) в худшем случае, где k является постоянным.
Эти проблемы называются податливыми , в то время как другие называются неразрешимыми или суперполиномиальными .
Формально алгоритм является алгоритмом полиномиального времени, если существует такой многочлен p (n) , что алгоритм может решить любой экземпляр размера n за время O (p (n)) .
Задача, требующая времени Ω (n 50 ), по существу неразрешима для больших n . Наиболее известный алгоритм полиномиального времени выполняется во времени O (n k ) для достаточно низкого значения k .
Преимущества в рассмотрении класса алгоритмов полиномиального времени заключаются в том, что все разумные детерминированные однопроцессорные модели вычислений могут быть смоделированы друг на друге с максимальным полиномиальным
NP-класс
Класс NP состоит из тех задач, которые проверяемы за полиномиальное время. NP — это класс проблем решения, для которого легко проверить правильность заявленного ответа с помощью небольшой дополнительной информации. Следовательно, мы не просим найти способ найти решение, а только для проверки того, что предполагаемое решение действительно является правильным.
Каждая проблема в этом классе может быть решена в экспоненциальном времени с помощью исчерпывающего поиска.
P против NP
Каждая задача решения, которая разрешима детерминированным алгоритмом полиномиального времени, также разрешима недетерминированным алгоритмом полиномиального времени.
Все проблемы в P могут быть решены с помощью алгоритмов полиномиального времени, тогда как все проблемы в NP — P неразрешимы.
Не известно, является ли P = NP . Однако в NP известны многие проблемы со свойством, что если они принадлежат P, то можно доказать, что P = NP.
Если P ≠ NP , то в NP есть проблемы, которых нет ни в P, ни в NP-Complete.
Задача принадлежит классу P, если ее легко найти решение. Проблема принадлежит NP , если легко проверить решение, которое, возможно, было очень утомительным.