класс сложности

В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности — это множества предикатов (функций, получающих на вход слово и возвращающих ответ 0 или 1), использующих для вычисления примерно одинаковые количества ресурсов. Для каждого класса существует категория задач, которые являются «самыми сложными» в данном классе. Это означает, что любая задача из класса сводится к такой задаче, и притом сама задача лежит в классе. Такие задачи называют полными задачами (англ. -complete) для данного класса. Наиболее известной полной задачей являются NP-полная задача. Полные задачи — удобный инструмент для доказательства равенства классов. Достаточно для одной такой задачи предоставить алгоритм, решающий её и принадлежащий более маленькому классу, и равенство будет доказано.