email@example.com wrote: > In article <firstname.lastname@example.org>, > KP Bhat <email@example.com> 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.
I would just add that we do know P != EXP, so at least one of the inequalities is strict.