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