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

Question

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?

Answer 1

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.

Answer 2

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

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

Answer 4

An example of a decidable, NP-Hard but not NP-Complete problem is the Towers of Hanoi problem. Intuitively, the T.of H. problem is not in NP because the exploration of all possible configurations cannot be done in polynomial time, on a non-deterministic machine.