One of the seven Millennium math problems for which you can earn a cool million dollars for proving or dis-proving the problem is P=NP. These terms refer to the complexity of math problems and the video in the next section explains the complexity universe pretty well. In its most simple terms, P is the set of all problems that are easy and that can be solved in polynomial time (a term that is based on the inputs, but means “fairly quickly”.) NP on the other hand, is the set of problems that are hard and cannot be solved in polynomial time.
One way to think of the problem is a jigsaw puzzle. Solving it might be hard (although not actually an NP problem), but checking that it was done correctly might only require a glance (a “P” or easy problem.) In the P/NP world, solving certain problems are hard, while checking them is frequently easy.
WHAT ARE THE IMPLICATIONS OF P=NP
If P=NP, then the world would be fundamentally transformed. All mathematical proofs would be trivial. Cryptology which is crucial for the everyday (like banking and your amazon shipments,) as well as for national security, would simply fade away as a tool.
Every branch of science would be also effected. In biology, the problems of protein folding would be easy. In physics, problems about the nature of the multiverse, might likewise seem trivial.
P=NP asks is it possible that solving a problem is as easy as checking a problem. If it could be proved that such is the case, it would have a profound impact on computer science, encryption and every branch of human discovery. No problem would be beyond solution. Interestingly, over time, the pool of high end math types has dropped the probability that a solution will be found from 20% to less than 10%. The smart money is now on proving P does not equal NP.
In the video below we learn about the taxonomy of Math Complexity. It is a great overview of the P vs NP world.
A SAMPLE PROBLEM
There are many samples of complex problems and one of the most famous is the Traveling Salesman problem whereby a salesman must travel a circuit visiting every city only once and returning to his home city while traveling the least possible number of miles. The problem is simple when there are just a few cities, but when the number is raised to say a thousand, the permutations become ridiculous and the problem becomes virtually unsolvable. It’s like playing chess … you can not evaluate every possible move as there are more possible moves than there are atoms in the universe. An example that is easier to understand is Sudoku. You can easily check whether a solution is valid, but solving the puzzle is much harder. But what if the same effort that went into checking the problem could solve the problem? That would be a massive breakthrough.
In the wizards opinion, perhaps quantum computing could solve some of the NP problems in the same order of magnitude of time (a requirement for any P=NP proof) as it takes to check a problem. Just 500 qubits, for example, would allow you to do 2^500 calculations in a single step. This represents a sum larger than all the atoms in the universe. If you could enter all possible Sudoku solutions or all possible chess moves at once, then perhaps a solution could be nearly instantaneous. No one really knows what is possible with this new technology. If there is to be a practical break though in the P=NP arena, it will almost certainly come from quantum computing.
I note that conventional wisdom is that QC will only be able to solve a small set of NP problems. (see video above.) Not sure that conventional wisdom will turn out to be right however.
The Traveling Salesmen Movie
For a fun movie for science geeks, try to find The Traveling Salesman (available on Amazon) which is about what happens to four math geniuses who solve the P=NP dilemma. Let us just say the government is keenly interested in their work. See the preview below:
The wizard gives it 5 stars for science geekery, but only 1 star for drama and action. So punk you have to ask yourself a question … are you a true geek or are you just another whinny mama’s boy that likes to watch things blow up? Well are you punk?
So Does P=NP?
With the yes side guess by experts now down to only 9%, it looks like the best chance for a proof may lie in the proof that the two are not the same and can never share the same space in a Venn diagram of mathematical complexity. Based on no evidence except a general belief that utilizing the computing power of multiple universes is going to be really useful, I belief that someday the solution to problems will exist in the same time approximation as the checking of a problem. Here is how really deep thinkers holding my point of view analyze this problem (Ok maybe they are on the other side.)
What could you do with a P=NP Computer?
For starters, If only P were truly equal to NP, then we could use the multi-verse computer to prove P=NP and thus win a million dollars. (In fact we could solve all the millennium challenges and win the remaining six million dollars.) Alas this a chicken and egg problem. BUT once you had such a device, you could crack every code, solve every problem in linear programming including any traveling salesman problem. You could solve any mystery in math, chemistry, information storage, and physics including how it will all end. Think about it, every mathematical conundrum solved just by asking.
Such a know everything computer could be asked about the problem of entropy ending the universe. One can imagine the computer swirling and whirring, seeking an answer to the unknowable. Over and over the question would be asked “How can we reverse entropy,” until finally, as the universe is about to go into it’s final phase of permanent stasis, the last of the NP problems finally submits to man’s insistence and the power of the multi-verse computer.
Imagine the scene as the last of the priests of the high tech world whispers the question one final time “How can we stop entropy from ending the universe?” Lights blink and the computer ponders this most severe of the NP problems before it finally says in a perfect Stephen Hawking voice …
“LET THERE BE LIGHT”
Note: The ending above, of course, is from Isaac Asimov’s famous short story The Last Question (A definite must read.)
Next Up: Why Terraforming Mars May Be Impossible (Oh Nooo.)