Если вы такой же программист, как и я, то вы, вероятно, знаете о нотациях Big-O, но знаете ли вы, что они относятся к разным классам сложности?

Классы сложности — это фундаментальная концепция информатики, описывающая ресурсы, обычно время и пространство, необходимые для решения задачи на компьютере. В этой статье мы рассмотрим наиболее часто изучаемые классы сложности и их отношения друг к другу.

Что такое класс сложности?

Класс сложности — это набор задач решения, которые могут быть решены с помощью алгоритма с определенным количеством ресурсов. Проблема принятия решения — это задача, в которой ответ либо да, либо нет, например, «является ли это число простым?» или «есть ли в этом графе гамильтонов цикл?»

Два наиболее часто используемых ресурса в теории сложности — это время и пространство. Время относится к количеству шагов, которые алгоритм выполняет для решения проблемы, а пространство относится к объему памяти, который требуется алгоритму.

Каждый класс сложности определяется набором проблем принятия решений, которые могут быть решены за определенное время или пространство. Например, класс P содержит все проблемы принятия решений, которые могут быть решены с помощью детерминированного алгоритма за полиномиальное время, а класс NP содержит все проблемы принятия решений, которые могут быть проверены за полиномиальное время с помощью недетерминированного алгоритма.

Класс P

Полиномиальное время означает, что время работы алгоритма ограничено полиномиальной функцией размера входных данных.

Некоторые примеры проблем в P включают сортировку списка чисел, поиск кратчайшего пути в графе и определение того, является ли число простым. Эти задачи считаются «легкими» в том смысле, что их можно относительно быстро решить на компьютере.

Класс НП

Класс NP, сокращение от «недетерминированное полиномиальное время», содержит все проблемы принятия решений, которые могут быть проверены за полиномиальное время с помощью недетерминированного алгоритма. Недетерминированный алгоритм — это теоретическая модель вычислений, в которой алгоритм может делать «догадки» и проверять правильность догадки за полиномиальное время.

Примером проблемы NP является проблема булевой выполнимости (SAT), которая спрашивает, существует ли присваивание булевых переменных, удовлетворяющее заданной булевой формуле. Хотя трудно найти удовлетворительное задание, относительно легко проверить правильность данного задания.

Хотя задачи NP в целом сложно решить, в NP есть некоторые проблемы, которые, как известно, решаются за полиномиальное время, например, поиск максимального потока в сети или проверка двудольности графа.

Класс NP-полный

Класс NP-Complete содержит все проблемы принятия решений, которые по крайней мере столь же сложны, как самые сложные проблемы в NP. Задача находится в NP-полной тогда и только тогда, когда она находится в NP и может быть сведена к любой другой задаче в NP за полиномиальное время.

Одной из самых известных NP-полных задач является Задача коммивояжёра (TSP), в которой требуется найти кратчайший возможный маршрут, проходящий через все города из заданного списка. Хотя TSP можно решить за экспоненциальное время, не существует известного алгоритма с полиномиальным временем, который решает все экземпляры задачи.

Класс NP-Hard

Класс NP-Hard содержит все проблемы принятия решений, которые не менее сложны, чем самые сложные задачи в NP-Complete. Задача находится в NP-Hard, если ее можно использовать для моделирования любой другой задачи в NP за полиномиальное время.

Некоторые примеры проблем NP-Hard включают проблему остановки, которая спрашивает, останавливается ли данная программа на заданном входе, и проблему выполнимости логической схемы, которая спрашивает, можно ли заставить данную логическую схему выводить определенное значение.

Класс EXPTIME

Класс EXPTIME, сокращение от «экспоненциальное время», содержит все проблемы принятия решений, которые можно решить за экспоненциальное время. Экспоненциальное время означает, что время работы алгоритма ограничено функцией, экспоненциальной по размеру входных данных. EXPTIME включает в себя множество проблем, которые слишком сложно решить на практике, например, проблему решения для логики второго порядка, которая спрашивает, истинно ли данное предложение во всех конечных структурах.

Класс PSPACE

Класс PSPACE содержит все проблемы принятия решений, которые могут быть решены с использованием полиномиального пространства на детерминированной машине Тьюринга. Этот класс включает задачи, которые находятся в P, NP, NP-Complete, NP-Hard и EXPTIME, поскольку любую задачу, которая может быть решена за полиномиальное время, также можно решить с использованием полиномиального пространства.

Некоторые примеры проблем в PSPACE включают определение победителя в игре в шахматы или проверку доказательства в логике высказываний.

Отношения между классами сложности

Отношения между различными классами сложности можно визуализировать с помощью диаграммы, называемой «зоопарком сложности». Вот упрощенная версия схемы:

           +---------------------+
           |      PSPACE         |
           +----------+----------+
                      |
         +------------+------------+
         |            |            |
    +----+----+  +----+----+  +----+----+
    |   NP    |  |NP-Complete|  | EXPTIME|
    +----+----+  +-----------+  +--------+
         |
    +----+----+
    |    P     |
    +---------+

Как показано на диаграмме, P является подмножеством NP, которое является подмножеством NP-Complete. PSPACE содержит все эти классы, а также EXPTIME. NP-Hard и EXPTIME не являются подмножествами какого-либо другого класса, поскольку они определяются с точки зрения их способности решать другие проблемы, а не их собственной разрешимости.

Заключение

В этой статье мы рассмотрели наиболее часто изучаемые классы сложности и их отношения друг к другу. В то время как некоторые задачи, такие как в P, могут быть решены относительно легко, другие, например, в NP-Complete или NP-Hard, в целом решить гораздо сложнее. Понимание классов сложности важно для ученых-компьютерщиков и математиков, работающих над проектированием и анализом алгоритмов, поскольку оно обеспечивает основу для понимания ограничений вычислительных ресурсов.

____________Спасибо, что прочитали 🙂________________

******************* ____Один 👏🏽 за следующую статью___******************