Excerpt

The triumphs of Kurt Gödel, Alan Turing, and Alonzo Church in the 1930s showed that some problems are infinitely hard. There are mathematical truths with no finite proof, no matter how long that proof can be. There are problems that no computer program can solve, no matter how long we let it run. These undecidability and uncomputability results placed fundamental limits on our ability—or any system’s ability—to prove and compute, and they reverberated throughout logic, mathematics, and the nascent field of computer science.

After the Second World War, as computing became more of a practical reality, the question was not “Can this problem ever be solved?” but “Can we solve it in a reasonable amount of time?” As computers became more powerful and capable of solving larger problems, it became more and more important to understand how the difficulty of these problems scales. If a problem twice as large takes just twice as long to solve, then larger and larger problems will quickly come within reach as our computers get faster.

Bibliography

Agrawal, M., N. Kayal, and N. Saxena. 2004. “Primes is in P.” Annals of Mathematics 160 (2): 781–793. https://doi.org/10.4007/annals.2004.160.781.

Edmonds, J. 1965. “Paths, Trees, and Flowers.” Canadian Journal of Mathematics 17:449–467. https://doi.org/10.4153/CJM-1965-045-4.

Karatsuba, A., and Y. Ofman. 1962. “Multiplication of Many-Digital Numbers by Automatic Computers.” Translation in the academic journal Physics-Doklady 7 (1963), pp. 595–596, Proceedings of the USSR Academy of Sciences 145:293–294.

Shor, P. W. 1994. “Algorithms for Quantum Computation: Discrete Logarithms and Factoring.” In SFCS ’94: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 124–134. USA: IEEE Computer Society. https://doi.org/10.1109/sfcs.1994.365700.

BACK TO Foundational Papers in Complexity Science