Мы можем сказать, что NP-полная задача — это задача, которая находится в NP и NP-трудна, но можем ли мы утверждать исключительно, что проблема NP-сложна только потому, что она NP-полна.
Пример: я свожу NP-полную задачу a к проблеме b. Таким образом, теперь доказано, что задача b является NP-полной. Могу ли я на самом деле сказать, что это также NP-сложно?
Определение полноты NP:
Задача Q является NP-полной тогда и только тогда, когда Q принадлежит NP и Q является NP-сложной.
Следовательно, да, мы можем совершенно определенно сказать, что любая NP-полная задача является NP-сложной по определению.
Обратите внимание, что в вашем вопросе есть небольшое искажение:
Пример: я свожу NP-полную задачу
aк проблемеb. Таким образом, теперь доказано, что задачаbявляется NP-полной.
Приведенный выше вывод верен только в том случае, если вы показали, что b находится в NP. Если b "сложнее", чем NP, то он не NP-полный. Обратите внимание, однако, что редукции достаточно, чтобы доказать, что b является NP-трудным.
