Чтобы доказать что-то NP-сложный, зачем вам переходить к NP-полной?

Question

Из википедии:

Задача H является NP-сложной, если и только если существует NP-полная задача L, которая за полиномиальное время сводится по Тьюрингу к H (т. Е. L ≤ TH).

Почему проблема (назовите ее W) уменьшается от необходимости завершения NP?Почему он не может быть просто NP-сложным?Кажется, что тебя волнует, что W "жесткий", не то, что в NP.

Мысли?

Answer 1

Может. Фактически, ваш второй абзац подразумевает первый абзац.

Предположим, что NP-трудная задача H полиномиально сводима к задаче X. По определению существует NP-полная задача C, полиномиально сводимая к H. Поскольку оба сокращения полиномиальны, вы можете привести C к X за полиномиальное время. Следовательно, NP-полная задача C сводится к X за полиномиальное время. Поэтому проблема X является NP-трудной.

Answer 2

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

Кроме того, вам не нужно доказывать твердость NP путем уменьшения, вы также можете доказать это непосредственно.