Search code examples
time-complexitycomputer-sciencenp

Let A be NP-complete and B be NP-hard. Can B be polynomial time reducible to A?

Let A be NP-complete and B be NP-hard. Can B be polynomial time reducible to A?

Ans: I know it can't be. Would the strong reason be, because NP-Complete is a subset of NP-Hard?

Solution

  • Let's first look at naming conventions of NP Hard and NP Complete (wikipedia):

    NP-hard
    Class of decision problems which are at least as hard as the hardest problems in NP. Problems that are NP-hard do not have to be elements of NP; indeed, they may not even be decidable.

    NP-complete
    Class of decision problems which contains the hardest problems in NP. Each NP-complete problem has to be in NP.

    NP-hard(B) are at least as hard as the hardest problem of NP.
    Hardest problems of NP are NP-complete(A).

    From these two statements, we can say that B is at least as hard as A.

    In simpler terms, this means that any algorithm for B immediately gives an algorithm for A. But the inverse is not true, knowing how to solve A doesn't tell us anything about how to solve B. This relation is not symmetric.

    This is why NP-hard is not reducible to NP-complete.