Show notes

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.

Class P:

Set of decision problems that can be solved in polynomial time (Easy to solve, easy to verify) Example: Multiplying numbers

Class NP:

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