Чтобы доказать что-то NP-Hard, почему вам нужно уменьшить к нему из NP-Complete?

Question

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

Проблема H - это NP-HAN, если и только в том случае, если есть проблема с NP-полной проблемой L, то есть полиномиальное время Turing-Undingiable для H (т. Е. L ≤ Th).

Почему проблема (называть ее), быть уменьшена от необходимости быть завершенным NP? Почему это не может просто быть NP-HARD? Похоже, что вы заботитесь о том, чтобы быть «жестким» не то, что его в НП.

Мысли?

Answer 1

Оно может. На самом деле, ваш второй абзац подразумевает первый абзац.

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

Answer 2

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

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