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:
“To be a philosopher is not merely to have subtle thoughts, nor even to found a school, but so to love wisdom as to live according to its dictates a life of simplicity, independence, magnanimity, and trust. It is to solve some of the problems of life, not only theoretically, but practically.”
—Henry David Thoreau (1817–1862)
““It’s hard to tell you how I managed it.
When I saw the shaft had me by the coat,
I didn’t try too long to pull away,
Or fumble for my knife to cut away,
I just embraced the shaft and rode it out....””
—Robert Frost (1874–1963)
“If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
—Barbara Coloroso (20th century)