In article <email@example.com>, KP Bhat <firstname.lastname@example.org> wrote: >The meaning of the word "hard" refers to time complexity. In order to >be NP-Hard, the time complexity should be worse than or equal to the >time complexity of a known problem in NP.
Even if "known problem in NP" is amended to "known NP-complete problem," this is inaccurate, and it's a common misconception, so it's worth clearing up. A problem is NP-hard if every problem in NP reduces to it ("reduce" here typically means polytime Karp reduction, but slight variants on this definition are also seen sometimes in the literature).
There are NP-complete problems that are solvable in time c^n for some constant c. It does not follow that, for example, a problem that is complete for DTIME(c^(2n)) is necessarily NP-hard. Just because the time complexity is greater doesn't automatically mean that there is a reduction.
This point is important because part of the reason that the P = NP conjecture is difficult is that we don't really understand well the relationship between nondeterminism and time complexity. One can prove the bounds P <= NP <= EXP but essentially nothing more precise is known. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences