NP-Complete vs. NP-hard [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 9 years ago.

Improve this question

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.

Answer 1

If A can be reduced to B in polynomial time all you know is that B is harder then 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

Answer 2

Since problem A can be reduced to problem B in polynomial time, any solution to problem B can be used to find a solution to A. Or more simply, solving A cannot be harder than solving B. Since we know A is NP-complete, which class of problems is at least as hard as NP-complete problems?

For reference you might also want to take a look at the wikipedia articles on NP-Hard (specifically the 2nd sentence), NP-Complete. and Reduction.

Answer 3

If A is NP-Complete, then it is also necessarily NP. This in turns means that every potential solution for A can be verified in polynomial time, which implies that the same is true for B (since A is reducible to B in polynomial time). Hence B is NP; it doesn't have to be stated as separate condition.