Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 clear idea about?

Thanks

share|improve this question
3  
You may also want to try asking on cstheory.stackexchange.com. –  KennyTM Sep 14 '10 at 9:37
    
I think this should be a Community Wiki question. –  Asaf Karagila Sep 14 '10 at 10:08
    
@KennyTM : Actually I'm often dubious, where to ask a question. Say, in Stackoverflow/Mathoverflow/MathSE/CSSE. But, it seemed any question is accepted here at any level. That's why I asked here. Thanks –  user1869 Sep 15 '10 at 11:15
add comment

5 Answers 5

up vote 11 down vote accepted

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.

share|improve this answer
    
Exactly what I was looking for. Thanks all. –  user1869 Sep 15 '10 at 11:56
add comment

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 HP 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 nondeterministic 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 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, than 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).

share|improve this answer
    
MathExchange is not a competition; but if you revised your response to include information from my answer, it would be nice if you would at least cite me. –  Niel de Beaudrap Sep 14 '10 at 14:49
    
I hope you'll believe me when I say that I edited my answer before reading yours... Great minds think alike, as they say. –  Gadi A Sep 14 '10 at 15:46
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
3  
Please define the problem (that is, what your input and output are). As I understand it, the usual Towers of Hanoi with three places is computationally very simple because the shortest sequence of moves is known analytically. –  Tsuyoshi Ito Nov 24 '10 at 20:24
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.