Классы сложности задач

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

• Абстракция результата
• Абстракция входных данных
• Абстракция алгоритма

Абстракция результата

В теории вычислимости рассматриваются только задачи с множеством значений {0; 1}, т.е. задачи, дающие положительный или отрицательный ответ на конкретный вопрос. Все остальные задачи сводятся к этому классу задач фиксацией искомого значения (напр. «Существует ли...?»). Переформулировка повышает сложность задачи не более чем полиномиально, а значит несущественно.

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

Абстракция входных данных

Для описания класса сложности входные данные описываются множеством условий I (напр. для задачи коммивояжёра I : G={V,E}, k, G — граф, k — искомое значение минимального пути), что затрудняет обобщение задачи. Поэтому вводится понятие строковой задачи — т.е. задачи получения из битовой строки длины(полученной конкатенацией битовых представлений всех исходных данных задачи) n ответа в виде I(n) → {0; 1}.

Абстракция алгоритма

Для унификации понятия «алгоритм» испольуется асимптотическое поведение его пространственной и временной сложности. Для градации уровней сложности используется вид алгебраической функции сложности. В основном различают уровни сложности $n^k$ (k — константа), $2^{n^k}$ и проч. Эта оценка должна быть верхней оценкой худшего случая работы алгоритма.

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

• P — полиномиальное время; наиболее часто используется в вычислениях, поскольку задачи этого класса могут быть решены за реальное время
• PSPACE — полиномиальные затраты памяти
• EXP — экспоненциальная временная сложность
• ESPACE — экспоненциальные затраты памяти
• NP — для задач этого класса неизвестны эффективные алгоритмы решения, поэтому рассматриваются алгоритмы проверки правильности решений (полный перебор вариантов)

Примеры задач различных классов сложности приведены в отдельной статье.

P vs NP

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

Задача называется NP-полной, если:

1. Эта задача принадлежит к классу NP
2. Любая задача, принадлежащая классу NP, полиномиально сводится к этой задаче

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

Если существует полиномиальный алгоритм решения для хотя бы одной NP-полной задачи, то за счёт второго условия было бы доказано, что P = NP.