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 is an enormous chasm between the relatively rich and powerful people who make decisions in government, business, and finance and our poorer neighbors who must depend on these decisions to alleviate the problems caused by their lack of power and influence.”
—Jimmy Carter (James Earl Carter, Jr.)
“It is what we imagine knowledge to be:
dark, salt, clear, moving, utterly free,
drawn from the cold hard mouth
of the world, derived from the rocky breasts
forever, flowing and drawn, and since
our knowledge is historical, flowing, and flown.”
—Elizabeth Bishop (1911–1979)
“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)