Talk:NP-complete problem

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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 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.


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.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:NP-complete_problem&oldid=15918467"