algorithmcomplexity-theorynp-completenp-hard

NP-Complete vs. NP-hard


If a problem A known to be NP-Complete can be reduced to another problem B in polynomial time then B is (A) NP-Complete (B) NP-hard

Nothing is given about problem B whether it is in NP or not. I'm confused because in Hopcraft and Ullman book there is theorem given if a NP-complete problem P1 can be reduced to problem P2 in polynomial time then P2 is NP-complete. But it also required for a problem to be NP-Complete that it should belong to NP class. Guys help in understanding this concept.


Solution

  • If A can be reduced to B in polynomial time all you know is that B is harder than A. In your case, if A is NP-complete, B is NP-hard.

    If B also happens to be in NP then B will be NP-complete (since NP-complete means being both in NP and being NP-hard at the same time).

    However, nothing stops you from reducing A to a problem that is not in NP. For example, it is trivial to reduce any problem in NP to the halting problem - a problem that is undecideable in addition to being NP-hard:

    Construct the following program:
        Test all possible solutions for A.
        If one of them is successful halt and otherwise enter an infinite loop.
    A has a solution if-and-only if that program halts