What does it mean for a problem to be NP Hard or NP Complete?
In: Mathematics
All the known algorithms for solving NP Complete problems require exponential time to solve. Choosing the well-known travelling salesman problem, if there are *n* cities for the salesman to visit then the time taken to find the shortest trip will be, at best, proportional to *x^(n)*, where *x*>1. People have found ways of reducing *x* to very close to 1 but solving really large problems is not practical.
One of the biggest problems in computer science is to prove (or disprove) that NP Complete problems require exponential time.
Latest Answers