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