Полиномиальное сокращение времени от NP Complete до других задач
Может кто-нибудь очистить мои сомнения, пожалуйста?
Предположим, у меня есть проблема A, которая, как известно, находится в NP-полной. и у меня есть другая проблема B, для которой мы не знаем класс сложности.
если я уменьшу A до B за полиномиальное время. мы можем сказать, что B также находится в NP-Complete.
но.. если я уменьшу B до A за полиномиальное время. почему я не могу сказать B также в NP-Complete?
2 ответа
если я уменьшу A до B за полиномиальное время. мы можем сказать, что B также находится в NP-Complete.
Нет, мы можем сказать, что B NP-жесткий. Полнота также требует членства в НП, что не следует из допущений.
Например, мы можем свести 3SAT к проблеме остановки. Проблема остановки не в NP (это даже не разрешимо).
если я уменьшу B до A за полиномиальное время. почему я не могу сказать B также в NP-Complete?
Можно сказать, что B находится в NP. Один алгоритм для B состоит в том, чтобы использовать сокращение и затем решить A. B может быть легкой проблемой, такой как "длина ввода нечетна".
Если A является NP-полным, вы можете уменьшить любую проблему в NP до A. Проблемы с NP-сложными являются самыми сложными в NP.
Если вы можете уменьшить A до B за полиномиальное время, это означает, что B "по крайней мере так же сложно, как" A, потому что, если вы можете решить B, тогда становится легко решить A. Таким образом, если A является NP-полным и те (по определению) самая сложная проблема в NP, B также является NP-полной (при условии, что B находится в NP, в противном случае это просто NP-сложная задача).
С другой стороны, способность уменьшать B до A - это все равно, что убивать муравья с помощью базуки. Вы, очевидно, можете сделать это, но это не значит, что убийство муравья является "базука-полным".