Определение NP Complete
Я пытаюсь понять формальное определение NP Complete и у меня возникли вопросы. Мне было интересно, если кто-то может предоставить больше понимания.
Книга алгоритмов Джона Кляйнберга говорит, что если каждая проблема NP может быть сведена к проблеме X, то проблема X находится в множестве NP Complete.
Теперь, поскольку P является подмножеством NP, из этого следует, что мы можем свести любую задачу в P к NP Полная задача за полиномиальное время. Это приводит к противоречию, что, поскольку редукция происходит за полиномиальное время, мы можем решить эту проблему NP Complete за полиномиальное время. Это не может быть правдой. Так что я не уверен, где это рассуждение неверно.
Также, если мы можем уменьшить любую проблему NP за полиномиальное время до NP Complete, то почему мы говорим, что NP Complete сложнее. Поскольку сокращение происходит за полиномиальное время, асимптотически это не должно иметь значения.
1 ответ
Теперь, поскольку P является подмножеством NP, из этого следует, что мы можем свести любую задачу в P к NP Полная задача за полиномиальное время. Это приводит к противоречию, что, поскольку редукция происходит за полиномиальное время, мы можем решить эту проблему NP Complete за полиномиальное время.
Вы неправильно поняли направление сокращения. Если вы можете свести любую NP-полную задачу к данной P-задаче, то P = NP, потому что это означает, что эта P-задача сложнее или эквивалентна любой NP-полной задаче. Тот факт, что проблема P может быть сведена к проблемам NP, не показывает, что она сложнее, чем NP, - это показывает, что она проще, чем NP, что не удивительно или противоречиво.
Притворимся, что мы можем сократить кратчайший путь до 1 прогона TSP, и притворимся, что TSP может быть решена только путем перечисления (экспоненциальная сложность). Тогда кратчайший путь полиномиален, редукция полиномиальна (O(1)), но TSP не полиномиален. Это гипотетический пример. Но, надеюсь, это показывает, что тот факт, что TSP может решить SP за один прогон, не означает, что TSP легко любой мерой. Сложность TSP не ограничена тем фактом, что он может легко решить SP.