Полный (сложность) - Complete (complexity)
 | Эта статья нужны дополнительные цитаты для проверка. (Октябрь 2008 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
В теория сложности вычислений, а вычислительная проблема является полный для класс сложности если это, в техническом смысле, одна из «самых сложных» (или «наиболее выразительных») задач в классе сложности.
Более формально проблема п называется жесткий для класса сложности C под данным типом снижение если существует редукция (данного типа) из любой задачи в C к п. Если проблема в обоих жесткий для класса и члена класса это полный для этого класса (для этого типа сокращения).
Проблема, полная для класса C как говорят C-полный, а класс всех задач полный за C обозначается C-полный. Первый полный класс, который должен быть определен и наиболее известный - это НП-полный, класс, содержащий множество трудных для решения проблем, возникающих на практике. Точно так же сложная задача для класса C называется Мангольд, например NP-жесткий.
Обычно предполагается, что рассматриваемое сокращение не имеет более высокой вычислительной сложности, чем сам класс. Следовательно, можно сказать, что если C-полный Если проблема имеет "простое в вычислительном отношении" решение, то все проблемы в "C" имеют "простое" решение.
Как правило, классы сложности, которые имеют рекурсивное перечисление, имеют полные проблемы, тогда как классы, не имеющие рекурсивного перечисления, не имеют их. Например, НП, со-НП, PLS, PPA все знали естественные полные проблемы, в то время как RP, ЗПП, BPP и TFNP не имеют известных полных проблем (хотя такая проблема может быть обнаружена в будущем).[нужна цитата ]
Есть занятия без полных проблем. Например, Sipser показал, что есть язык M такой, что BPPM (BPP с оракул M) полных проблем нет.[1]
Рекомендации
- ^ Сипсер, Майкл (1982). «О релятивизации и существовании комплектаций». Автоматы, языки и программирование. Конспект лекций по информатике. 140. С. 523–531. Дои:10.1007 / BFb0012797. ISBN 978-3-540-11576-2.