How much would you like one million dollars?
I for one would.
I can imagine endless sleep-filled nights with that amount snoozing soundly in my bank account. To get it, I could rob a bank, be lucky and successful in business, poison my parents surreptitiously, or simply solve P vs NP.
If you do solve it, the Clay Mathematics Institute will send you that right away.
The problem is, of course, that even the greatest mathematicians on our planet can’t do it, and that has huge implications for our surge into artificial intelligence and its applications.
Now, not being a professor or reader in pure mathematics or computer science, you're going to have to read this knowing I had to ask where to write my name on my maths O level exam. However, that has never stopped us before, so let's proceed.
The key to this is algorithms.
Those are what are driving our ability to create artificial intelligence. An algorithm itself is even difficult to define, but generally it's a set of dynamic and interactive instructions used to solve problems by artificial intelligent ‘beings’, like computers or robots.
These beings can solve many challenges via algorithmic deduction and process, but they have to do it in a reasonable amount of time. I can certainly paint the Forth Bridge (which it is said needs repainting upon completion as it takes that long to decay), but the time it would take me would be far too long to be useful, viable, or ever repeated.
In a similar way, algorithms need to solve in polynomial time, P, which has an end and is useful, and not in nondeterministic polynomial time, NP, which basically goes on forever, and while we may know the algorithm is doing the right thing we will certainly die before we know the answer.
The concept was explored by Douglas Adams in The Hitchhiker's Guide to the Galaxy, in which the supercomputer Deep Thought spends seven-and-a-half million years working out the answer to the ultimate question. Unfortunately, we don't know what that question was, but we do know the process showed NP to not equal P.
Other examples of the challenge are quite mind-boggling. For example, let's consider the famous Traveling Salesperson conundrum.
An algorithm that can quickly determine the shortest route for the salesperson to visit all the cities on their itinerary just once, and return them to where they started is impossible.
Why is it impossible?
Well, because it would take an algorithm about one-thousand steps to solve that problem with just ten cities. If we’re looking at twenty cities, more than one million. If our salesperson had to do this for all three-hundred major population cities in the US say, the algorithm would still be running as we abandoned Saturn to live on Pluto.
I would, of course, have inherited my parents millions by then, so that's something.
Another strange example.
It’s wedding time. And our happy couple have forty-eight guests arriving in a few months to celebrate with them, and they need to seat them optimally, where everyone will be next to their family and friends, and no-one will attack their neighbor with the asparagus spears.
Given the list of attendees, their preferences and table-related elements like mandatory presence at a certain table, or how many can sit at each, an algorithm could never determine completely the perfect seating arrangement.
Again you ask why.
Okay well, an algorithm would need to consider over three-hundred million possible options just for the first table of eight at a forty-eight person affair alone. It’d need to process over seventy-five million steps or options for the next table, and so on. By the time the plan was finished completely the couple would not only be divorced but dead. For millennia.
There are many other examples of problems that algorithms can never solve completely, from a simple sudoku grid to why I’m still surprised when my printer actually prints. We’d know if the algorithm was working correctly, and we could very quickly check that the solution is indeed correct at the very end, but for them to get from NP to P - from conceptual to useful - is to this day still impossible.
Solve P vs NP, and you win a million. Solve the P vs NP challenge and you change the world forever.
And you’ll be more than just a millionaire.
picture by Karolina Grabowska
