history of complexity theory

Stephen Cook. Toronto. Realizes you can reduce the boolean satisfiability problem (called SAT) to the quintessential NP class.

Not enough time to write a full paper, he quickly types up the report for a conference. He might finish it afterwards.

Conference time. Paper is presented, and people find it sort of interesting, as far theoretical computer science goes. Cook himself found it sort of cool as well.

But then. A bunch of problems were shown to be reducable to SAT.

Bang.

Now if you solved SAT (in polynomial time), you also solved a ton of other really important problems. Like world-changing level.

So world changing, the clay institute of mathematics is giving a 1 million dollar prize to whoever can prove SAT is or is not in P.

It's still up for grabs. 50 years since Cook published the original paper.