A New Approach Breaks A Barrier That’s Stood For Nearly Half A Century – Planning The Best Route With Multiple Destinations Is Hard Even For Supercomputers
Computers are good at answering questions. What’s the shortest route from my house to Area 51? Is 8,675,309 a prime number? How many teaspoons in a tablespoon? For questions like these, they’ve got you covered.
There are certain innocent-sounding questions, though, that computer scientists believe computers will never be able to answer – at least not within our lifetimes. These problems are the subject of the P versus NP question, which asks whether problems whose solutions can be checked quickly can also be solved quickly. P versus NP is such a fundamental question that either designing a fast algorithm for one of these hard problems or proving you can’t would net you a cool million dollars in prize money.
My favorite hard problem is the traveling salesperson problem. Given a collection...