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:
“There are nowadays professors of philosophy, but not philosophers. Yet it is admirable to profess because it was once admirable to live. 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 is hard living down the tempers we are born with. We
all begin well, for in our youth there is nothing we
are more intolerant of than our own sins writ large in
others and we fight them fiercely in ourselves; but we
grow old and we see that these our sins are of all sins
the really harmless ones to own, nay that they give a
charm to any character, and so our struggle with them
dies away.”
—Gertrude Stein (1874–1946)
“The wisest thing a parent can do is to let preschool children figure out themselves how to draw the human figure, or solve a whole range of problems, from overcoming Saturday-morning boredom to dealing with a neighborhood bully. But even while standing on the sidelines, parents can frequently offer support in helping children discover what they want to accomplish.”
—John F. Clabby (20th century)