Become a fan of Slashdot on Facebook

 



Forgot your password?
typodupeerror

Comment Re:P=PN (Score 4, Informative) 222

You're really close!

For NP-complete you need a slight modification of the traveling salesman problem. An example would be that you need to visit 5 cities, but you need to travel less than 50 miles. Is there a route that will get you through all 5 cities in less than 50 miles?

To find a solution need to search through all the permutations (factorial time), but to verify that you have a solution is polynomial time.

However, your original traveling salesman problem is NP-hard because there is no way to verify that you have the shortest route without calculating all of the routes.

I probably have an advantage here because read the Sipser book less than a year ago. Let's see what I remember in another three years. ;)

Slashdot Top Deals

"Card readers? We don't need no stinking card readers." -- Peter da Silva (at the National Academy of Sciencies, 1965, in a particularly vivid fantasy)

Working...