Example of a problem that is NP-Hard but not NP-Complete

Please, mention one problem that is NP-Hard but not NP-Complete? And, explain why.

I see some papers assert Degree Constrained Minimum Spanning Tree is an NP-Hard problem and some say it's NP-Complete. Why so? Is it something that we don't have a clear idea about?

Solution 1:

The difference is that NP-complete means both NP-hard and in NP. Sometimes it's not important to mention that something is in NP even if it is, so NP-hard is said instead. I don't think there's some sophisticated motive behind it.

The halting problem is a classical example of NP-hard but not in NP problem; it can't be in NP since it's not even decidable, and it's NP-hard since given any NP-language $L$ and an NP machine $M$ for it, then the reduction from $L$ to halting problem goes like this:

Reduce the input $x$ to the input $(M',x)$, where $M'$ is a machine that runs $M$ on $x$ in all the possible ways ($M$ is non-deterministic, so there are several such ways, but a finite number since $M$ is polynomial), and halts if $M$ accepts in at least one of these computations.

Of course, $M'$ is not polynomial, but the reduction (producing $(M',x)$ given $x$) is polynomial, so this is a polynomial-time reduction.

Sometimes people are not satisfied with HP (halting problem) since it's undecidable. It's much more difficult to give a concrete example of a decidable problem, since most of the everyday problems are in PSPACE and it is yet unknown if PSPACE is different than P (if it is, then every PSPACE-complete language, such as TQBF (the language of all true quantified boolean formulas) will do. For now, we need to go as far as NEXP-complete problems (since the hierarchy theorems show that NP is different than NEXP).

Complete problems for NEXP can be constructed from complete graph problems for NP (such as Hamiltonian cycle) if we change the representation of the graph - instead of being given directly, it is given via a black-box algorithm that takes two vertices as input and outputs whether there is an edge between them or not (so the size of the representation of the graph is exponentially smaller than it would be for if the edges were given directly).

Solution 2:

I will answer the following part of the question:

And, explain why. I see some papers assert Degree Constrained Minimum Spanning Tree is an NP-Hard problem and some say it's NP-Complete. Why so?

Some people say “the Degree Constrained Minimum Spanning Tree problem (DCMST) is NP-hard” for a reason, other people say “DCMST is NP-complete” for a different reason.

As is explained in the other answers, the word “NP-complete” means that a problem belongs to NP and is NP-hard. Note that NP is a class of decision problems (that is, problems whose answers are yes/no). Some people avoid saying “DCMST is NP-complete” and choose to say “DCMST is NP-hard” because DCMST is a function problem (that is, not a decision problem) and therefore cannot belong to NP by definition.

However, this is not the end of the story. Other people do say “DCMST is NP-complete.” When they say this, they consider the decision version of the problem implicitly:

The function version of DCMST: Given a graph G with edge weights and a positive integer d, find a minimum-weight spanning tree of G whose maximum degree is at most d.
The decision version of DCMST: Given a graph G with edge weights and positive integers d and k, decide whether G has a spanning tree whose maximum degree is at most d and whose total weight is at most k.

Therefore, if you accept the convention to refer to the decision version as DCMST, it is perfectly fine to say that DCMST is NP-complete. In computational complexity theory, this convention is often used.

Note that the decision version of DCMST can be solved in polynomial time if and only if the function version of DCMST can be (“if” is easy, “only if” is slightly more difficult). This is why calling the function version and the decision version by the same name causes little confusion.

Solution 3:

As noted in the earlier answers, NP-hard means that any problem in NP can be reduced to it. This means that any complete problem for a class (e.g. PSPACE) which contains NP is also NP-hard.

In order to get a problem which is NP-hard but not NP-complete, it suffices to find a computational class which (a) has complete problems, (b) provably contains NP, and (c) is provably different from NP. So:

While PSPACE contains NP, and has complete problems, the containment is not yet known to be strict. Therefore,PSPACE-complete problems do not suffice.
The same goes for any complete problem for any class in the polynomial hierarchy. If the hierarchy does not collapse, any complete problem for any class in the hierarchy (aside from P, NP, or coNP) would suffice; but without a proof that the PH doesn't collapse, we can't use such problems
We can prove that NEXP (the class of problems solvable in exponential time on a nondeterministic Turing Machine) strictly contains NP, and has complete problems. So any NEXP-complete problem is NP-hard but not NP-complete.

Solution 4:

Verification of NP-Complete problem's solution is easy, i.e., given a solution it can be verified in polynomial time. This property is not true for NP-Hard problems. Towers of Hanoi is a NP-Hard problem which is not NP-Complete, since its solution itself is of exponential length. Here, solution means the step by step moves of disks; not the algorithm (or program which can be written in 3 lines using recursion).

Solution 5:

What is the next best move in the game of chess?

Answer to this problem is difficult to compute and difficult to verify as well. Same goes with

Optimization problem of traveling salesman i.e. What is the shortest circuit for the salesman?

Hence both are NP-Hard but not NPC. You might ask

How NPH and NPC are different?

To which I'll answer
It is not that simple, what we have been taught (in grad schools) is a mere surface of it. This goes deep, way deep. Even I don't know much about these classes in a great detail, they aren't that easy. But to put it in simple words...

The problems which can be solvable by a deterministic Turing Machine (DTM) in polynomial time are called problems in $P$ class. OR The problems whose solution you can find easily and those solutions can be checked easily.
The problems which can be solvable by a non-deterministic Turing Machine (NDTM) in polynomial time, are called problems in $NP$ class. OR problems whose solution isn't easy to find, but given a solution it is easy to check if its correct or not. For example solving a nxn Sudoku, difficult to solve but easy to check a given solution.
Before moving further, you should be aware of the concept of reduction. A problem, say problem1, can be reduced to another problem, say problem2, IF solving problem1 is as hard as solving problem2. In simple words, if problem2 is a big bad problem and problem1 is just a small specific version of that. Therefore we say problem1 $\le_P$ problem2. For example:
3x3 Sudoku $\le_P$ 9x9 Sudoku $\le_P$ Samurai Sudoku $\le_P$ nxn Sudoku $\le_P$ Graph Coloring Problem.
Now there are some problems that are at least as hard as the hardest problems in $NP$ but they do not lie in $NP$. You might ask, why? because their solution couldn't be verified that easily. Like the aforementioned chess one or optimizing version of TSP. These problems are $NP-Hard$. Another property of these problems is, problems in $NP$ can be reduced to problems in $NP-Hard$.
There exists an intersection of $NP$ and $NP-Hard$ which is called $NP-Complete$. Solutions to the problems in NPC can be verified easily and they are solvable by a NDTM. But they also belong to NPH because some problems in NP can be reducible to problems in NPC. Therefore it has properties of both NP and NPH.