Some clarification regarding P
Q1> All NP problems are polynomial time reducible to an NP-COMPLETE Problem.
So are all NP-COMPLETE problems polynomial time reducible to an NP Problem?
Q2> All NP-COMPLETE problems and NP problems are polynomial time reducible to an NP-HARD Problem.
So are all NP-HARD problems polynomial time reducible to an NP/NP-COMPLETE Problem?
Q3> An NP-HARD problem need not be in NP, so why is NP-Hard definition on NP ?
EDIT :
Not a duplicate of np-vs-np-complete-vs-np-hard-what-does-it-all-mean:
I am asking something else here- like, are the reductions One-way, or both way possible ? And my 1st question on NP-Hard is building over what had been discussed there.
No, reductions are one-way, not both-ways. If you can solve problem A using a solution to problem B, this does not always mean that you can solve problem B using a solution to problem A.
This is very well illustrated by your first question,
Q1. So are all NP-COMPLETE problems polynomial time reducible to an NP Problem?
Definitely not, unless P=NP. Note that even P problems are NP (you do not need any certificate to check the answer for P problems), but you can not reduce an NP-complete problem to a P problem unless P=NP (if a NP-complete problem is reduced to a P-problem, this immediately means that P=NP).
Note that it all stands only unless P=NP. If it turns out that P=NP, than it is easy to see that any NP problem can be reduced to any other NP problem.
BTW, your questions are not quite clear when you say "...polynomial time reducible to an NP Problem". Do you mean any NP-problem or at least one NP-problem? If you mean any , my answer above stands. If you mean "are all NP-COMPLETE problems polynomial time reducible to at least one NP Problem?", that the answer is yes, definitely: every problem can be reduced to itself.
链接地址: http://www.djcxy.com/p/39938.html上一篇: 完成pr0blem也NP
下一篇: 关于P的一些澄清