Каковы примеры проблем NP, которые сводятся к NP-полному, но не наоборот?
Каковы примеры NP-задач, которые сводятся к NP-полной проблеме, но не наоборот? Когда я читал о NP и NP-complete, я думал, что отображение будет одно-одно, так что глупо классифицировать их. Тем не менее, безусловно, есть проблемы, которые могут быть сведены только в одном направлении. Мне интересно их знать.
1 ответ
Все проблемы NP могут быть сведены к задачам NP-complete. NP-полные задачи - это особый тип NP-задач. Следовательно, NP-полные проблемы не нужно уменьшать, чтобы считать их находящимися в NP; они уже в NP.