Forgot your password?
typodupeerror

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

by razberry636 (#36024644) Attached to: Forty Years of P=NP?
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. ;)

Elegance and truth are inversely related. -- Becker's Razor

Working...