Является ли NP-полным pr0blem также NP-твердым?

Question

Можно сказать, что NP-полная проблема - это проблема с NP и NP-hard, но можем ли мы утверждать исключительно, что проблема NP-hard связана исключительно с тем, что она NP-полная.

Пример: Я уменьшаю NP-полную проблему a к проблеме b. Поэтому в настоящее время проблема b оказалась NP-полной. Могу ли я сказать, что он тоже NP-жесткий?

Answer 1

Определение NP полноты:

Проблема Q является NP-полной, если и только если Q в НП и Q является NP-трудной.

Таким образом, да, мы можем с уверенностью сказать, что любая NP-полная проблема NP-hard, по определению.

Обратите внимание, что у вас есть небольшое искажение в вашем вопросе:

Пример: Я уменьшить NP-полной задачи a к проблеме b. Поэтому в настоящее время проблема b оказалась NP-полной.

Вышеуказанный вывод выполняется только в том случае, если вы указали b, чтобы быть в NP. Если b «сложнее», чем NP, то это не NP-complete. Обратите внимание, однако, что сокращения достаточно, чтобы доказать, что b NP-жесткий.