В теории сложности вычислений вычислительная задача считается решённой для некоторого класса сложности , если она, в техническом смысле, относится к числу «самых сложных» (или «самых выразительных») задач в данном классе сложности.
Более формально, задача p называется сложной для класса сложности C при заданном типе редукции , если существует редукция (заданного типа) любой задачи из C к p . Если задача является одновременно сложной для класса и члена класса, она является полной для этого класса (для этого типа редукции).
Задача, полная для класса C, называется C-полной , а класс всех задач, полных для C, обозначается как C-полный . Первый полный класс, который был определен и наиболее известен, — это NP-полный , класс, который содержит много трудноразрешимых задач, возникающих на практике. Аналогично, задача, сложная для класса C, называется C-трудной , например, NP-трудной .
Обычно предполагается, что рассматриваемое сокращение не имеет более высокой вычислительной сложности, чем сам класс. Поэтому можно сказать, что если C-полная задача имеет «вычислительно простое» решение, то все задачи в «C» имеют «простое» решение.
Как правило, классы сложности, имеющие рекурсивное перечисление, имеют известные полные проблемы, тогда как классы, не имеющие рекурсивного перечисления, не имеют ни одной. Например, NP , co-NP , PLS , PPA все имеют известные естественные полные проблемы.
Существуют классы без полных проблем. Например, Сипсер показал, что существует язык M, такой что BPP M ( BPP с оракулом M ) не имеет полных проблем. [1]