If any problem P is NP complete then if there is a polynomial time reduction of P to another problem R then what can we say about R.Is it NP-hard or NP complete ?
From Theory of computation of Hopcroft,Ullman theorem 10.4 it says it would be NP complete but there some times when i see that it is NP-Hard in some other reference . is there any condition when it is NP Hard or NP Complete .Or i misunderstood the theorem .
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Check the definition of NP-completeness: an NP-complete problem is an NP-hard problem that's in NP. $\endgroup$– David RicherbyCommented Feb 13, 2014 at 19:18
-
$\begingroup$ if it is not known that if R is in NP or not that is it is a new unknown problem. only there is reduction of P to R. $\endgroup$– TcKOCommented Feb 14, 2014 at 7:15
-
$\begingroup$ Exactly: you don't know that $R$ is in NP. So can you say that $R$ is NP-complete? $\endgroup$– David RicherbyCommented Feb 14, 2014 at 8:22
-
$\begingroup$ so one can say it would be definitely in NP-hard .But if u see the theorem i mentioned above says that it would be Np complete. $\endgroup$– TcKOCommented Feb 14, 2014 at 10:54
-
$\begingroup$ Correct: you only know it's NP-hard and it might not be NP-complete. I think you must've misunderstood the theorem since Hopcroft and Ullman wouldn't get that wrong. $\endgroup$– David RicherbyCommented Feb 14, 2014 at 12:16
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
NP-hard means that all the problems in NP reduces to this. NP-complete means that it is in NP as well.
Sometimes we say a problem is NP-hard when it is obviously NP-complete. But this is because we want to stress the hardness of the problem, and also that it should be trivial that the problem is in NP.
answered Feb 13, 2014 at 20:29
$\begingroup$
$\endgroup$
A problem L is NP-complete when:-
- L $\epsilon$ NP
- Every problem L' $\epsilon$ NP, L' is polynomial time reducible to L
For at least property 2 satisfied but do not know if 1st property (or not necessarily property 1) is satisfied by a problem L, then L $\epsilon$ NP-Hard.
For proving a problem satisfies property 1, best we can do is check if for any given input an algorithm can verify the solution in polynomial time, i.e., problem is polynomial time verifiable given a certificate of a solution as input.
For proving a problem satisfies property 2, it is difficult to prove all L' individually are polynomial- time reducible to L. Hence we make use of transitivity property of the polynomial reductions.
If we are able to show that a problem L'' already known to be in NP-complete to be polynomial-time reducible to the problem L, then L satisfies property 2 by transitivity.
Transitivity - If L1 is polynomial-time reducible to L2 and L2 is polynomial-time reducible to L3, then L1 is polynomial-time reducible to L3 by transitivity.
So, every L' is polynomial-time reducible to L'' (already NP-complete) and we prove L'' is polynomial-time reducible to L implies every L' is polynomial-time reducible to L.
In the case in the question, P (= L'') is already known to be in NP-complete. So, P is polynomial-time reducible to R(= L) implies R satisfies property 2. Hence, R $\epsilon$ NP-Hard for sure. For R $\epsilon$ NP-complete it requires to be NP too.
