In 2000, the Clay Mathematics institute listed Their Millennium Prize Problems - 7 problems in mathematics with a prize of 1 million dollars each for anyone with a correct solution. P vs NP was one of them.
In computer science we like to categorize problems. One way to categorize them is based on how hard they are to solve.
Set of decision problems that can be solved in polynomial time (Easy to solve, easy to verify) Example: Multiplying numbers
Set of decision problems for which the answer (yes or no) can be verified in polynomial time. (Not easy to solve but easy to verify a potential solution) Example: Sudoku
Obviously P is a subset of NP One of the biggest questions in computer science is : is NP a subset of P? To me, it seems like being able to find the solution to a problem and being able to verify that solution are fundamentally different. P vs NP is asking whether that is really the case.
Aside: Beyond P and NP
There are problems that we KNOW are hard to solve (EXPTIME)
- problems that we know are neither easy to solve nor easy to verify (exp in both)
- Ex: Chess
- Given a random snapshot of a board, it is not obvious what is the best move to make, and it is equally difficult to verify that a move that was made was the correct one
There are even problems that we know are undecidable
- Halting problem
But how could we go about trying to prove that NP is actually part of P?
Stephen Cook and Leonid Levin
Cook Levin theorem
- Boolean satisfiability problem (SAT) is NP Complete.
- proved that SAT is the hardest problem in NP and that any problem in np can be reduced to SAT
- NP problem -> SAT A consequence of this proof is that if we find a polynomial time solution to SAT, we’ve proven that there exists a polynomial time solution to every NP problem and this would prove P vs NP
Another result of SAT = NP Complete: This allowed us to find hundreds of more NP complete problems like Sudoku, Battleship, Tetris, Super Mario brothers
- Because if you can reduce SAT -> a problem, that problem is also NP complete
- All these also became “the hardest problems in NP”
- Now if we can show that any one of these problems can be solved in polynomial time (or that it’s impossible to do this) we’ve proven/disproven P vs NP
What would happen if we proved P = NP
But most scientists and mathematicians believe that P does not equal NP Lots of problems that we believed to be hard to solve, would actually be possible
- Transportation of all forms could be scheduled optimaly
- Cryptography relies on the hope that prime factorization is hard
- Biology -> protein folding