Computer scientists, both classical and the quantum kind like me, traditionally divide the world into two problems that can be solved easily (= scales polynomially in time with more inputs) and not so easily (= scales exponentially). The former class of problems are formally called P and the latter NP. The reason this is a big deal and why you should at least be aware of this is because NP problems dominate the internet: E.g., search, ‘traveling salesmen’ (= what your GPS does but also pretty much any optimization problem ) and factorization (on which almost all of internet security – including your amazon purchases – relies on). And if you are not convinced that any of the above matter, then you obviously belong to the Facebook generation. If this is the case, let me blow your mind by saying that, in fact, finding the largest clique (friends who are all friends with each other) on Facebook is also a NP problem (whaaaat! OMG!).
Proving or disproving P = NP holds the coveted spot as the computational challenge of the century. With a bounty of $1 million on its head, it is one of the 7 Millennium Prizes posted by the Clay Institute. And it’s the only one that has the potential to solve any and all of the other 6 prizes — prove that P= NP, then you have in your hands 1 million dollars, plus with a little bit of work, $6 million more. Because if P = NP, literally everything in the world can be solved by a computer, much to the dismay and pleasure of the technology singularists. In fact, one could even write a program to solve every problem in the world, including customized Cancer and Alzheimer prevention and treatment.
To prove P ≠ NP one has to show that no P algorithm (known or unknown) can solve any NP problem. Its almost impossible to prove a negative. But hope lies in the qualifier ‘almost’. Most mathematicians and computer scientists believe that P ≠ NP. In case you are wondering how anyone would go about something like this, here’s a sampler of the two best attempts at this $1 million prize:
1. Liar’s Paradox: Liar’s paradox refers to the statement “This sentence is false”. Think over it for a minute, and you will see why both the possibilities are not possible. Hence the paradox. Liar’s paradox has been around since the 600 B.C, but it was Kurt Gödel who shot it into the Hall of Fame by using this approach to upend the very foundations of Mathematics. Gödel incompleteness theorems show that elementary arithmetic cannot be both consistent and complete and caution you against the rather moody nature of self-referential statements that contain negatives (hmm, is that why my grammar teacher cautioned me against double negatives?).
Back to the million dollar question at hand (literally, ha!). A similar approach can be used to prove P ≠ NP, using efficient and trickily self-referential algorithms. For an easy-to-digest detailed discussion see Lance Fortnow’s awesome book The Golden Ticket: P, NP, and the Search for the Impossible
2. Circuits: This approach uses the digital circuitry idea that any function can be computed by a combination of AND, OR and NOT logic gates (the teeny guys that make up any smart chip). Every P problem has a reasonably small circuit using these logic gates. If we can show that some computationally hard problem cannot have small circuits, then we can show NP ≠ P by translating a this computer science problem into an electronics problem.
Most computer scientists think of P ≠ NP as the problem of the century. If you have any ideas of putting this to rest, you should get cracking! And oh, if P=NP, watch out: the world as you know it will change dramatically. As the featured image hints, creativity (along with everything else) will become automated.
Image courtesy: Theory Matters