
Re: On NP Completeness and Intractability
Posted:
Oct 25, 2005 6:30 PM


In article <1130277999.884543.197050@g43g2000cwa.googlegroups.com>, KP Bhat <kbhat@sta.samsung.com> wrote: >The meaning of the word "hard" refers to time complexity. In order to >be NPHard, 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 NPcomplete problem," this is inaccurate, and it's a common misconception, so it's worth clearing up. A problem is NPhard 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 NPcomplete 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 NPhard. 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 tchowatalumdotmitdotedu The range of our projectileseven ... the artilleryhowever 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

