NP-Complete vs. NP-hard [closed]

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 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