- Alan Turing's 1936 paper laid the foundations of computer science, introducing the Turing machine and proving unsolvable problems like the halting problem.
- Algorithmic shortcuts like Dijkstra's algorithm and Karatsuba's multiplication allow computers to solve problems quickly without checking every possible solution.
- The Traveling Salesman Problem (TSP) is computationally hard, leading to the theory of NP-completeness where many problems are interconnected in difficulty.
- P versus NP is a major open question in computer science, with implications for cryptography, AI, quantum computing, and our understanding of computation.
- Tim Roughgarden is a professor specializing in algorithms, algorithmic game theory, and the connections between computer science and economics.