| Sumario: | The article refers to a 1971 research paper by Steve Cook, "The Complexity of Theorem-Proving Procedures" and focuses on computational complexity. The Polynomial Time (P) versus Nondeterministic Polynomial-Time (NP) problem in computer science is discussed, as well as the theory of efficient algorithms for a solution to NP-complete problems. Integer programming, approaches to proving that P≠NP such as diagonalization, circuit and proof complexity with Boolean operators, brute force and heuristics, NP-complete optimization and the limits of approximation, hardness assumptions in cryptography, and the elimination of randomness are mentioned.
|
|---|