Pour prouver que quelque chose est du NP-DUR, pourquoi devez-vous y réduire à partir d'un NP-complete?

Question

De Wikipedia:

Un problème H est du NP-Duron si et seulement s'il y a un problème NP-Complete L qui est le temps polynomial turing-réductible à H (c'est-à-dire L ≤ Th).

Pourquoi le problème (l'appelle w) est-il réduit de la fin de NP-Complete? Pourquoi ne peut-il pas aussi être NP-dur? Cela semble être ce que vous vous souciez d'être "dur" pas que c'est en NP.

Les pensées?

Answer 1

Ça peut. En fait, votre deuxième paragraphe implique le premier paragraphe.

Supposons que le problème du NP-dur H est polynomialement réductible au problème X. Par définition, il existe un problème NP-complete C qui est polynomialement réductible à H. Étant donné que les deux réductions sont polynomiales, vous pouvez réduire C à x en temps polynomial. Par conséquent, le problème NP-Complete C est réductible à X en temps polynomial. Par conséquent, le problème x est du NP-dur.

Answer 2

Si vous pouvez réduire polynomialement un problème NP-durs à votre problème, cela est suffisant pour prouver le NP-Dardness de votre problème. Cependant, un problème NP-dur spécifique peut ne pas être polynomialement réductible à votre problème, même s'il est en main np lui-même.

De plus, vous n'avez pas à prouver le NP-Durness par réduction, vous pouvez également le prouver directement.