NP-Complete vs NP-hard

Question

If task A, known as 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 in NP or not. I am confused, because in the book of Hopcraft and Ullman there is a theorem, if the NP-complete problem P1 can be reduced to the problem P2 in polynomial time, then P2 is NP-complete. But it also required the problem to be NP-Complete, that it must belong to the class NP. Guys help to understand this concept.

Answer 1

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

If B is also in NP, then B will be NP-complete (since NP-complete means that both are NP and simultaneously NP-rigid). A.

However, nothing prevents you from decreasing A to a problem that is not in the NP. For example, it is trivial to reduce any problem in NP to a problem with stopping - a problem that cannot be solved in addition to 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 A. Or, more simply, solution A cannot be more difficult than solution B. Since we know that A is NP-complete, which class of tasks is at least as complex as NP-complete problems?

For reference, you can also take a look at wikipedia articles on NP-Hard (specifically the second sentence), NP-Complete . and reduction .

Answer 3

If A is NP-Complete, then it is also required NP. This in turn means that each potential solution for A can be checked at polynomial time, which means that the same is true for B (since A is reducible to B at polynomial time). Therefore, B is NP; it does not need to be specified as a separate condition.