# Thread: difference between np complete and np hard

1. ## difference between np complete and np hard

greetings!!!
could anybody tell me the difference between np hard and np complete (in simple way). I have read articles on many sites but they are a bit complex.
now this is what I think
np complete problems are those problems whose solution can be verified in polynomial time by a non deterministic turing machine.
np hard problems are the hardest problems whose solution might not be verifiable.
please do correct me if i am wrong.
also a problem is np hard if there exist np complete problem that is reducible to np harp problem

thanks

2. np complete problems are those problems whose solution can be verified in polynomial time by a non deterministic turing machine.
No. First, either a solution has to be found by a nondeterministic TM or a solution and a proof that it is indeed a solution have to be verified by a deterministic TM. (Both variants have to be done in polynomial time.) And then such problem is called to be in NP, not NP-complete.

np hard problems are the hardest problems whose solution might not be verifiable.
Usually one deals with decidable problems when talking about NP-complete, NP-hard, etc. Thus, solutions to such problems can not only be verified, but also found.

also a problem is np hard if there exist np complete problem that is reducible to np harp problem
Yes. This can be taken as a definition.

Basically, a problem P is called NP-hard if every problem in NP is polynomial-time reducible to P. A problem is called NP-complete if it is NP-hard and it itself is in NP. Thus, NP-hard problems can be harder than NP-complete ones.

The Wikipedia article describes this pretty well.

3. 1) a np problem is the decision problem whose solution can be found in polynomial time by non deterministic TM and whose solution is verifiable in polynomial time by deterministic TM.
2) a problem c is np complete problem if it is in np and every np problem is reducible to c in polynomial time
3) a problem k is np hard if its at least as hard as hardest problem in np and there exist np complete problem which is polynomial time reducible to np hard.
hope I am correct ( if am not then do tell me)

4. 1) a np problem is the decision problem whose solution can be found in polynomial time by non deterministic TM and whose solution is verifiable in polynomial time by deterministic TM.
First, the two conditions joined by "and" are equivalent. It's not like you need both of them. Second, it is important to understand what "whose solution is verifiable in polynomial time" means. It's not that you have a deterministic TM such that you give a problem and a hypothetic answer, e.g., "yes", and it verifies whether the answer is correct. I don't have time at the moment to write the precise definition, but see it explained here.

2) a problem c is np complete problem if it is in np and every np problem is reducible to c in polynomial time
Yes.

3) a problem k is np hard if its at least as hard as hardest problem in np and there exist np complete problem which is polynomial time reducible to k.
Again, these two conditions are equivalent (roughly speaking); you only need one of them.

5. is it true that all np complete problems are not reducible to np hard (such problems are in np)
reason:-
suppose there are 3 problems 1) A (which is np) 2) B (which is np complete) 3) C (which is np hard).
now A is reducible to B (as every np problem is reducible to np complete) which is further reducible to C (np complete problem is reducible to np hard)or we may say A is reducible to C it means A is np and reducible to np hard problem and hence A should be np complete (which is contradictory to our assumption that a is np not np complete)

6. will there be a new class (say super hard) if np hard problems are reducible to some single problem ( as np complete problems are reducible to np hard problems)

7. is it true that all np complete problems are not reducible to np hard (such problems are in np)
All problems in NP (including NP-complete ones) are poly-time reducible to any NP-hard problem.

it means A is np and reducible to np hard problem and hence A should be np complete
It does not follow that A is NP-complete.

8. will there be a new class (say super hard) if np hard problems are reducible to some single problem ( as np complete problems are reducible to np hard problems)
As far as I know, there is an infinite hierarchy. $\mathrm{NP}=\Sigma^p_1\subseteq\Sigma^p_2\subseteq \dots$ (polynomial hierarchy). All these problems are decidable. Then there are semi-decidable problems, denoted by $\Sigma^0_1$, which are properly contained in $\Sigma^0_2\subset\Sigma^0_3\subset\dots$ (arithmetic hierarchy).

Of course, the hardest of all problems is the Ultimate Question of Life, the Universe, and Everything (and we already know the answer!).

9. so is it this way
np problem:- problem that can be solved in polynomial time by non deterministic turing machine or whose solution can be found in polynomial time by deterministic turing machine.
np complete:- a problem is np complete if every np problem is reducible to np complete in polynomial time.
np hard:- problems at least as hard as np complete and there should exist np complete problem reducible to np hard.
but how can we decide if a problem is only np or np complete or np hard???

10. np problem:- problem that can be solved in polynomial time by non deterministic turing machine
Yes.

or whose solution can be found in polynomial time by deterministic turing machine.
No. In my opinion, to solve a problem is the same thing as to find its solution. Therefore, "problem that can be solved in polynomial time" (from the first quote) is the same thing as problems "whose solution can be found in polynomial time" (from the second quote); however, in the first quote you require nondeterministic machines while in the second quote you require deterministic ones. That's why, in my opinion, the second quote is incorrect.

The important thing about the second variant is that together with a problem, one gives to a deterministic machine a polynomial-size proof, also called certificate, that the answer is "yes". The machine then verifies not just the answer "yes" but the fact that the proof is correct. The machine does not have to discover this proof; in fact, it can be discovered in polynomial time only by a nondeterministic machine. More formally (see this lecture from Brown University): A language (set of problem instances for which the answer is "yes") L is called to be in NP if there exist a polynomial p and a polynomial-time deterministic machine M such that for every problem instance x, x is in L iff there exists a proof y such that |y| <= p(|x|) and M(x,y) = "yes". (Here |x| and |y| are sizes of x and y, respectively.)

np complete:- a problem is np complete if every np problem is reducible to np complete (which one?) in polynomial time.
No, this is NP-hard. See the definition in post #2 above.

np hard:- problems at least as hard as np complete and there should exist np complete problem reducible to np hard.
These two conditions are equivalent.

but how can we decide if a problem is only np or np complete or np hard???
It may not be easy. You can show that a problem is in NP by definition. To show that a problem L is NP-complete you show that it is in NP and that another NP-complete problem (and therefore all problems in NP) is reducible to L. To show just that L is NP-hard you prove the second part only.

11. Formal overview
NP-complete is a subset of NP, the set of all decision problems whose solutions can be verified in polynomial time; NP may be equivalently defined as the set of decision problems that can be solved in polynomial time on a nondeterministic Turing machine. A problem p in NP is also in NPC if and only if every other problem in NP can be transformed into p in polynomial time. NP-complete can also be used as an adjective: problems in the class NP-complete are known as NP-complete problems.
taken from wiki.
so I guess every np problem is reducible to np complete and some np complete problem are reducible to np hard ( am i correct!!!)

12. some np complete problem are reducible to np hard
Every problem in NP (including NP-complete ones) is reducible to every NP-hard problem.