This article originally appeared on Motherboard Germany. Since its original publication it has been updated with new information by Motherboard US.
What do curable cancer, fair capitalism, and the perfect game of Super Mario Bros. all have in common? Per a mathematical theory, the solution to any one of these problems would allow us to quickly solve the others. All that’s needed are better algorithms to prove that complicated questions—such as protein folding, efficient marketplaces, and combinatorial analyses—are merely variations of simpler problems that supercomputers are already able to solve.
But how can one algorithm simplify extremely complicated problems? That depends on another question: What if complicated problems are really just simple problems in disguise? This riddle remains one of the biggest unsolved questions of modern mathematics, and is one of the seven Millennium Prize Problems, for which every accepted answer is rewarded with one million dollars.
Now, a German man named Norbert Blum has claimed to have solved the above riddle, which is properly known as the P vs NP problem. Unfortunately, his purported solution doesn’t bear good news. Blum, who is from the University of Bonn, claims in his recently published 38-page paper that P does not equal NP. In other words, complicated problems are fundamentally different than straightforward problems and it doesn’t look like our high-performance computers will be able to crack these most difficult problems anytime in the near future. And in the days since his paper was published, numerous mathematicians have begun to raise questions about whether Blum solved it at all.
Videos by VICE
What exactly is the P versus NP Problem?
Most computer scientists tend to agree with Blum’s conclusion. Hard problems are hard, easy problems are easy.
In computer science, easy problems usually fall under the banner of P. This means that they can be solved in “polynomial time,” which is a lot like saying that they can be solved in a reasonable period of time. Much more difficult are the NP problems, which computers are unable to solve in a reasonable time frame. For practical purposes, NP problems might as well just be unsolvable by computers. (Note, however, that NP stands for “nondeterministic polynomial time” rather than “not polynomial” time.)
Here are some examples of NP problems:
Protein folding: The process through which proteins in a biological organism obtain their structure. Better insight into this process could help us recognize or even hinder mutations, which could cure certain forms of cancer.
Optimized routefinding: An optimized travel route through 15 different cities without visiting the same city twice? A hard nut to crack, even for a supercomputer, which is why this is also considered an NP problem in computer science.
The perfect chess game: A game of chess has infinite possible moves, such that even a supercomputer with incredible capacity cannot determine a perfect tactic. Many mathematicians consider this problem so difficult that they don’t deem it an NP problem, but rather consider it completely out of the realm of possibility.
All of these complex problems have one thing in common: As difficult as it may be to find a solution to NP problems, it’s relatively easy to check the validity of the solutions once you have them.
These two categorical distinctions in problem complexity have origins before the societal rise of home computers. In the 1970s, when computers still were the size of a clunky fridge, it was quickly determined that not all of mankind’s problems could be simply solved by those machines. It was proposed that the distinction could be formalized in terms of computational complexity, leading to a suite of complexity classes, including N and NP.
Since of the formal definition of P and NP in 1971, computer scientists have debated whether or not it would be possible to come up with an algorithm capable of reducing or redefining NP problems such that they can be solved in polynomial time. Should someone be able to prove that all NP problems are ultimately just variations of P problems, then all NP problems would essentially be subject to the same form of reduction. In other words, whoever knows the perfect Super Mario Bros. tactic could also cure cancer.
In total, 116 of the bravest in their field have officially attempted to solve this mystery (though untold more computer scientists have posted would-be solutions to messageboards and on sites like arXiv). To date, none of these proofs have officially been recognized by the mathematics community.
A Sort of Who Wants to be a Millionaire? for Mathematicians
In 2000, the Clay Mathematics Institute (CMI), located in Oxford, compiled a list of seven unsolved Millennium Prize Problems, pledging one million dollars for each solution. It’s a sort of Who Wants to be a Millionaire? or X Prize for mathematicians.
The Millennium Prize Problems are considered exceptionally difficult even in expert circles. A wealth of field-specific knowledge is necessary to even understand the questions. The only Millennium Prize Problem solved to date is the Poincaré conjecture, which is not easily explained as an aside in an article about a different mathematics concept.
Solving the NP problem wouldn’t be an altogether good thing. For example, most encryption is based on the difficulty of factoring very large prime numbers. Integer factorization is a class NP problem. A 256-bit code, such as the ones financial institutions use in online credit card payments, is considered unbreakable, and thus very safe. Should someone prove that NP does equal P, banks would have to quickly come up with a different security method.
What do mathematicians think of Blum’s mathematical proof?
Since Blum’s paper was published, mathematicians and computer scientists worldwide have been racking their brains as to whether the Bonn-based researcher has, in fact, solved this Millennium Prize Problem. After an initially positive reaction, such as the one from Stanford mathematician Reza Zadeh, doubts are beginning to arise about whether Blum’s reasoning is correct.
In a forum for theoretical mathematics, a user named Mikhail reached out to Alexander Razborov—the author of the paper on which Blum’s proof is based—to ask him about Blum’s paper. Razborov purports to have discovered an error in Blum’s paper: Blum’s main argument contradicts one of Razborov’s key assumptions. And mathematician Scott Aaronson, who is something of an authority in the math community when it comes to P vs. NP, said he would be willing to bet $200,000 that Blum’s mathematical proof won’t endure.
“Please stop asking,” Aaronson writes. If the proof hasn’t been refuted, “you can come back and tell me I was a closed-minded fool.”
In the week since Aaronson’s initial blog post, other mathematicians have begun trying to poke holes in Blum’s proof. Dick Lipton, a computer science professor at Georgia Tech, wrote in a blog post that Blum’s proof “passes many filters of seriousness,” but suggested there may be some problems with it. A commenter on that blog post, known only as “vloodin,” noted that there was a “single error on a subtle point” in the proof; other mathematicians have since chimed in and confirmed vloodin’s initial analysis, and so the emerging consensus among many mathematicians is that a solve for P vs. NP remains elusive.
Translated by Melina McCormack.
