Типы классов сложности | P, NP, CoNP, NP жесткий и NP полный

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

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

Классы сложности полезны при организации схожих типов задач.

Типы классов сложности

В данной статье рассматриваются следующие классы сложности:

1. Класс Р
2. НП класс
3. Класс CoNP
4. НП жесткий
5. НП завершено

Класс Р

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

Функции:

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

Этот класс содержит множество естественных задач, таких как:

1. Вычисление наибольшего общего делителя.
2. Нахождение максимального паросочетания.
3. Варианты решений линейного программирования.

НП класс

NP в классе NP означает недетерминированное полиномиальное время . Это набор задач принятия решений, которые могут быть решены недетерминированной машиной за полиномиальное время.

Функции:

1. Решения класса NP трудно найти, поскольку они решаются недетерминированной машиной, но решения легко проверить.
2. Проблемы NP можно проверить на машине Тьюринга за полиномиальное время.

Пример:

Давайте рассмотрим пример, чтобы лучше понять класс NP. Предположим, есть компания, в которой работает 1000 сотрудников с уникальными идентификаторами сотрудников. Предположим, что для них доступно 200 комнат. Выборка из 200 сотрудников должна быть объединена в пару, но у генерального директора компании есть данные некоторых сотрудников, которые не могут работать в одном помещении по личным причинам.
Это пример задачи NP. Так как легко проверить, является ли данный выбор из 200 сотрудников, предложенных коллегой, удовлетворительным или нет, т.е. ни одна пара, взятая из списка сотрудников, не появляется в списке, данном генеральным директором. Но создание такого списка с нуля кажется настолько сложным, что совершенно непрактичным.

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

Этот класс содержит много проблем, которые хотелось бы эффективно решать:

1. Булева проблема выполнимости (SAT).
2. Проблема гамильтоновых путей.
3. Раскраска графа.

Класс Co-NP

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

Функции:

1. Если проблема X находится в NP, то ее дополнение X' также находится в CoNP.
2. Для задач NP и CoNP нет необходимости проверять все ответы сразу за полиномиальное время, нужно за полиномиальное время проверять только один конкретный ответ «да» или «нет», чтобы задача находилась в NP или СоНП.

Некоторые примеры проблем для C0-NP:

1. Проверить простое число.
2. Целочисленная факторизация.

NP-тяжелый класс

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

Функции:

1. Все NP-трудные проблемы не в NP.
2. Их проверка занимает много времени. Это означает, что если дано решение NP-сложной задачи, то проверка правильности этого решения занимает много времени.
3. Задача A называется NP-трудной, если для каждой задачи L из NP существует полиномиальное сведение от L к A.

Некоторые из примеров проблем в Np-hard:

1. Проблема остановки.
2. Квалифицированные булевы формулы.
3. Гамильтонов цикл отсутствует.

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

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

Функции:

1. NP-полные задачи особенные, поскольку любая задача класса NP может быть преобразована или сведена к NP-полным задачам за полиномиальное время.
2. Если бы можно было решить NP-полную задачу за полиномиальное время, то можно было бы решить и любую NP-задачу за полиномиальное время.

Вот некоторые примеры проблем:

1. 0/1 Рюкзак.
2. Гамильтонов цикл.
3. Выполнимость.
4. Вершинное покрытие.

Для получения более подробной информации см.:
Проектирование и анализ алгоритмов.