Полная (сложность) - Complete (complexity)

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

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

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

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

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

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

использованная литература