Классы задач

18 декабря 2023 г.

Это краткий конспект части о классах задач в книге Гид по Computer Science, Вильям Спрингер.

Классификация задач по времени, которое занимает их решение, в зависимости от количества входных данных. Благодаря такой классификации задач мы определяем сложность их решения.

1) Класс P - (за полиномиальное время). Самые простые. Все задачи, у которых время решения — количество входных данных, возведенное в некоторую постоянную степень. Например сортировка списков.

Класс P собственное подмножество множества задач EXP, которые решаются за экспоненциальное время; любая задача, которая может быть решена за время O(n^2), также может быть решена за время O(2^n).

2) Класс NP, недетерминированный полином (Nondeterministic Polynomial, NP).- Также входит в множество EXP. Задача может быть решена недетерминированно за полиномиальное время. (Детерминированный алгоритм с фиксированными входными данными каждый раз проходит через одну и ту же последовательность состояний и возвращает один и тот же результат. С математической точки зрения такой алгоритм отображает область экземпляров задачи на ряд решений. Недетерминированный алгоритм может демонстрировать различное поведение для одного и того же набора входных данных.)

То есть существует алгоритм, который решает эту задачу путем принятия ряда решений, причем в каждой точке принятия решения алгоритм случайным образом (и удачно) делает правильный выбор. Пока остается ряд шагов ведущих к ответу, алгоритм выбирает правильные шаги. Решение такой задачи можно проверить (детерминированно, то есть следуя предварительно определенной последовательности шагов) за полиномиальное время.

NP надмножество P; любое решение, которое может быть найдено за полиномиальное время, также может быть проверено за полиномиальное время. Но также еще существует нерешенная проблема - Проблема P = NP: это одно и то же множество или же P является собственным подмножеством NP?

NP-сложная задача (несколько рекурсивно) определяется как любая задача, которая по крайней мере столь же сложна, как и самая сложная задача класса NP. Если у нас есть оракул, который дает ответ на задачу C, то мы можем (за полиномиальное время) преобразовать его в ответ на задачу B. Решение задачи является NP-сложным, если любая задача класса NP может быть сведена к этому решению. NP-сложная задача не обязательно должна принадлежать к классу NP;

Задача, которая и является NP-сложной, и относится к классу NP, называется NP-полной.

Если NP-полная задача имеет псевдополиномиальное решение, она называется слабо NP-полной. Если же это не так (или P = NP), то задача называется сильно NP-полной.

Другие классы, как правило, определяются в терминах машин Тьюринга.