Why Some NP Problems Are Hard To Solve
Because of the many important problems in this class, there have been extensive efforts to find polynomial-time algorithms for problems in NP. However, there remain a large number of problems in NP that defy such attempts, seeming to require super-polynomial time. Whether these problems really aren't decidable in polynomial time is one of the greatest open questions in computer science (see P=NP problem for an in-depth discussion).
An important notion in this context is the set of NP-complete decision problems, which is a subset of NP and might be informally described as the "hardest" problems in NP. If there is a polynomial-time algorithm for even one of them, then there is a polynomial-time algorithm for all the problems in NP. Because of this, and because dedicated research has failed to find a polynomial algorithm for any NP-complete problem, once a problem has been proven to be NP-complete this is widely regarded as a sign that a polynomial algorithm for this problem is unlikely to exist.
However, in practical uses, instead of spending computational resources looking for an optimal solution, a good enough (but potentially suboptimal) solution may often be found in polynomial time. Also, the real life applications of some problems are easier than their theoretical equivalents. For example, inputs to the general Travelling salesman problem need not obey the triangle inequality, unlike real road networks.
Read more about this topic: NP (complexity)
Famous quotes containing the words problems, hard and/or solve:
“Hats have never at all been one of the vexing problems of my life, but, indifferent as I am, these render me speechless. I should think a well-taught and tasteful American milliner would go mad in England, and eventually hang herself with bolts of green and scarlet ribbon—the favorite colour combination in Liverpool.”
—Willa Cather (1876–1947)
“And even my sense of identity was wrapped in a namelessness often hard to penetrate, as we have just seen I think. And so on for all the other things which made merry with my senses. Yes, even then, when already all was fading, waves and particles, there could be no things but nameless things, no names but thingless names. I say that now, but after all what do I know now about then, now when the icy words hail down upon me, the icy meanings, and the world dies too, foully named.”
—Samuel Beckett (1906–1989)
“You who were directionless, and thought it would solve everything if you found one,
What do you make of this? Just because a thing is immortal
Is that any reason to worship it? Death, after all, is immortal.
But you have gone into your houses and shut the doors, meaning
There can be no further discussion.”
—John Ashbery (b. 1927)