50 years since publishing the Cook's Theorem
Abstract
Algorithms are the essence of Informatics and of some classical parts of Mathematics too. But until the 1930s algorithms were considered only as a tool for solving important for science and practice tasks. Since the term is not formal, only from this moment the algorithms are an object of study that raised a number of important issues. For example, can the concept of algorithm be formalized? What tasks can be solved algorithmically and are there any tasks that cannot be solved with an algorithm? Why do different algorithms for the same task work for a significantly different time? Therefore, we can safely say that the foundations of the Mathematical Theory of Algorithms (which is the subject of this article) were laid in the 1930s. The year 2021 marks the 50th anniversary of the publication of a very important result of the theory and the exposition in this article focuses on this result and the following challenge that has not received an answer yet.
References
N. Chomsky. Three models for the description of language. IRE Transactions on Information Theory, 2 (1956), 113–124.
A. Church. An unsolvable problem of elementary number theory. American Journal of Mathematics, 58 (1936), 345–363.
S. A. Cook. The complexity of theorem proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971, 151–158, doi:10.1145/800157.805047.
M. R. Garey, D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness (ed. W. H. Freeman), 1979, ISBN 0-7167-1045-5.
S. C. Kleene. λ-definability and recursiveness. Duke Mathematical Journal, 2, No 2 (1936), 340–352, doi:10.1215/s0012-7094-36-00227-2.
E. Post. Finite Combinatory Processes – Formulation 1. Journal of Symbolic Logic, 1 (1936), 103–105.
A. M. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42 (1936), 230–265. DOI:10.1112/plms/s2-42.1.230.
L. A. Levin. Universal'nyye zadachi perebora. Problemy peredachi informatsii, 9, No 3 (1973), 115–116.
A. A. Markov. Teoriya algorifmov. Moskva, Izd. AN SSSR, 1954.