Monday, February 26, 2007

First Formalization of NP-completeness

While I was looking at the subset-sum-problem (in cryptography, we call it knapsack), I came across the original paper (The Complexity of Theorem Proving Procedures) submitted to 1971 ACM Symposium on Theory of Computing by Stephen Cook who formalized the notion of NP-completeness in this paper. The paper left unsolved the greatest open question in theoretical computer science - whether complexity classes P and NP are equivalent.

No comments: