What makes an NP-hard problem not to be an NP-complete problem?

I am having confusion about NP-hard problems.

Some NP-hard problems are in NP which are called NP-Complete and some are not in NP.

For ex : Halting problem is only NP-hard, not NP-complete.

But why it is not NP-complete ? I mean what property should a problem have to qualify as

"NP-hard 开发者_Go百科but not NP-complete problem" ?

---

I think the shortest answer is: NP-complete = NP-hard AND in NP.

Thus, to show that a problem is NP-complete you must show that it is both NP-hard and in NP. Typically, showing that a problem is in NP is pretty easy (just give a non-deterministic polynomial time algorithm). Showing that a problem is NP-hard is, well, hard. Thus, even in a proof of NP-completeness, most of the proof is dedicated to the NP-hardness.

As for the halting problem, it fails to be in NP, and thus is not NP-complete.

---

What defines NP is the fact that you can verify a solution of a NP problem in polynomial time. Thus if a problem is NP-hard, but not NP-complete, you can't verify a solution to the problem in a theoretically timely manner. This makes sense if you look at the Halting problem. The solution is either 'yes' or 'no', which you can only verify by solving the original problem again, meaning it's not in NP.

---

NP-hard simply means "at least as hard as a problem in NP". NP-complete means "in NP, all NP-complete problems can be reduced to this problem and this problem can be reduced to all NP-complete problems".

The Wikipedia article is probably a good starting point, as it specifically talks about the Halting Problem as one of its illustrations.

---

Short answer: The only NP-hard problems which are not NP-complete are the ones which are not part of NP.

Long answer:

Now, why is that? Let's look at the definition of NP-complete and NP-hard carefully:

A problem X is NP-complete if:

1. It is in NP

2. Every problem in NP is reducible to X in polynomial time.

A problem X is NP-hard if it satisfies (2) ((1) is not a necessary condition).

Out of these definitions it's obvious to conclude that the only problems which are NP-hard but not NP-complete are the ones out of NP.

For instance, all the NP-hard problems which are not decision problems are not NP-complete (since NP by definition is formed with decision problems). In particular, the search version of the Travelling Salesman problem: Given a list of cities and their pairwise distances, the task is to find the shortest possible route that visits each city exactly once and returns to the origin city.

The search version of the TSP is proven to be NP-hard, but since it's not a decision problem (you cannot solve it by answering yes or no to a question) it's not part of NP and thus cannot be NP-complete.

The halting problem is a decision problem, but it's not verifiable in polymonial time (the second requirement for a problem to be in NP by definition) that's why it cannot be NP-complete.