Классификация вычислительных задач по степени сложности. Классы сложности задач P и NP. NP сложные и NP трудные задачи

По книге Системы искусственного интеллекта

По интернетам

Классы задач в зависимости от их трудности

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

2. Труднорешаемые задачи (вероятно, сложные задачи). Это задачи, для решения которых, по-видимому, не существует полиномиального алгоритма. Иными словами, для их решения, скорее всего, существуют только экспоненциальные алгоритмы.

3. NP-задачи (NP — аббревиатура для «недетерминированные полиномиальные»). Это класс задач, которые мы можем решить за полиномиальное время, если угадаем, какой путь вычислений необходимо выполнить. Грубо говоря, этот класс включает в себя все задачи, которые имеют экспоненциальный алгоритм, но не доказано, что они не могут иметь полиномиального алгоритма.

4. Р-задачи (Р — аббревиатура для «полиномиальный»). Этот класс включает в себя задачи, которые имеют полиномиальные алгоритмы. Большинство людей считают, что этот класс является собственным подклассом класса 3.

По википедии

Классы сложности

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

Класс P

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

Класс NP

Класс NP содержит задачи, которые недетерминированная машина Тьюринга в состоянии решить за полиномиальное количество шагов от размера входных данных. Их решение может быть проверено детерминированной машиной Тьюринга за полиномиальное количество шагов. Следует заметить, что недетерминированная машина Тьюринга является лишь абстрактной моделью, в то время как современные компьютеры соответствуют детерминированной машине Тьюринга с ограниченной памятью. Поскольку детерминированная машина Тьюринга может рассматриваться как специальный случай недетерминированной машины Тьюринга, класс NP включает в себя класс P, а также некоторые проблемы, для решения которых известны лишь алгоритмы, экспоненциально зависящие от размера входа (то есть неэффективные для больших входов). В класс NP входят многие знаменитые проблемы, такие как задача коммивояжёра, задача выполнимости булевых формул, факторизация и др.