Если L2 является NP-полным и L1 ≤p L2, я могу видеть, что L1 является NP в любой момент времени. И я считаю, что L1 может быть сложным для NP (хотя и не всегда). Теперь мой вопрос: кажется, что в некоторых случаях NP hard можно свести к NP. Я просто не уверен, правильно ли мое предположение, и может потребоваться разъяснение.
Когда L2 является NP полным, а L1 может быть уменьшен до L2
Ответы (1)
Проблема в NP означает: есть алгоритм, который работает в NP для решения проблемы. Проблема NP-сложная означает: эта проблема "по крайней мере так же сложна, как самые сложные проблемы в NP" Проблема NP-полная означает: эта задача находится в NP и NP-трудна.
Таким образом, редуцируя за полиномиальное время NP-трудную задачу L1 к другой задаче L2, вы доказываете, что L2 также является NP-сложной. Но в этом случае L2 не нужен в NP.
person
fireabend
schedule
13.09.2019
