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:
“The problems of victory are more agreeable than the problems of defeat, but they are no less difficult.”
—Winston Churchill (1874–1965)
“The repugnance to animal food is not the effect of experience, but is an instinct. It appeared more beautiful to live low and fare hard in many respects; and though I never did so, I went far enough to please my imagination.”
—Henry David Thoreau (1817–1862)
“All the sciences are now under an obligation to prepare for the future task of philosopher, which is to solve the problem of value, to determine the rank order of values.”
—Friedrich Nietzsche (1844–1900)