Talk:NP-completeness/Archive 1

This page is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Thanks for filling this gap! I have three suggestions:

the mentioning of the alternate definition of reducibility should probably be moved to the end of the article, so as to not confuse the general flow of argument. It doesn't seem to be nearly as important as truly understanding what reducibility means.
I believe one can make a case that the NP-complete ones are the hardest in NP: as soon as I can solve an NP-complete one (even if I need exponential time), I can then solve all NP problems with only a moderate slowdown.
The points about P problems not necessarily being easy to solve are all well taken, but should probably be moved to the article that describes the two classes P and NP. --AxelBoldt

You're welcome. Of your three bullets, I'd have no problem with the first and third. Feel free to implement those.

For the second bullet, I had said NP-complete problems are the hardest in NP in the first sentence of my article, but wanted to give some caveats to that near the end. I was trying to address a misconception I've seen before. Some people think that the definition of NP-complete is "the most difficult problems in NP". They are then confused when they learn that there might be NP problems with the same time complexity that aren't in NP-complete. They are even more confused when they learn that there may be an NP problem that is not in NP-complete, but that is more difficult than a given NP-complete problem by a factor of O(n^1000).

If we want an intuitive description of NP-complete, I'd recommend "the NP problems most likely to be superpolynomial" rather than "the hardest problems in NP". Yes, I do sometimes use the phrase "the hardest problems in NP" with my students, but I then go on to give the caveats that I gave in that article. I then say "most likely to be difficult" rather than "the most difficult". That seems to work well. YMMV. -LC

I see. Yes, we explain in what sense the NP-complete problems are the "toughest" and that there may non-complete problems with even longer running times.

Axel, I see you incorporated David Eppstein's answer. That was good. We ought to also give an example of a problem that is known to be NP*C but suspected to not be NPC.

I wouldn't know one, but maybe Eppstein does :-) --AxelBoldt