Полный (сложность)

В теории сложности вычислений является вычислительная задача полной для определенного класса сложности , если она в техническом смысле относится к числу «самых сложных» (или «наиболее выразительных») задач в этом классе сложности.

Более формально, проблема p называется сложной для класса сложности C при заданном типе редукции , если существует редукция (данного типа) от любой проблемы из C к p . Если проблема одновременно сложна и для класса, и для члена класса, она решена для этого класса (для этого типа сокращения).

Задача, полная для класса C, называется C-полной , а класс всех задач, полных для C, называется C-полной . Первый полный класс, который необходимо определить, и наиболее известный — это NP-complete , класс, который содержит множество труднорешаемых задач, возникающих на практике. Аналогично, задача, сложная для класса C, называется C-трудной , например NP-трудной .

Обычно предполагается, что рассматриваемая редукция не имеет большей вычислительной сложности, чем сам класс. Следовательно, можно сказать, что если C-полная задача имеет «вычислительно простое» решение, то все проблемы в «C» имеют «легкое» решение.

Как правило, классы сложности, имеющие рекурсивное перечисление, имеют полные проблемы, тогда как классы, у которых нет рекурсивного перечисления, не имеют ни одного. Например, NP , co-NP , PLS , PPA имеют известные естественные полные проблемы.

Есть занятия без полных проблем. Например, Сипсер показал, что существует язык M такой, что BPP ^М ( BPP с oracle M ) не имеет полных проблем.