All geek questions in one place

To prove that something is NP-hard, why do you need to reduce it to NP-complete?

From Wikipedia:

Problem H is NP-rigid if and only if there exists an NP-complete problem L, which is the polynomial time reduced by Turing to H (i.e., L≤TH).

Why is the problem (call it W) reduced from having to be NP-complete? Why can't it just be NP-solid? It seems that you make sure that W is “tough” and not that it is in NP.

Thoughts?

+3
source share
2 answers

He can. In fact, your second paragraph implies the first paragraph.

, NP- H X. NP- C, H. , C X . NP- C X . X NP-.

+3

NP- , NP- . NP-hard , NP-hard.

, NP- , .

0

Source: https://habr.com/ru/post/1758452/

More articles:


All Articles