Turing’s algorithmic lens: From computability to complexity theory
DOI:
https://doi.org/10.3989/arbor.2013.764n6003Keywords:
Computational complexity, the permanent problem, P and NP problems, Interactive proofs and holographic proofsAbstract
The decidability question, i.e., whether any mathematical statement could be computationally proven true or false, was raised by Hilbert and remained open until Turing answered it in the negative. Then, most efforts in theoretical computer science turned to complexity theory and the need to classify decidable problems according to their difficulty. Among others, the classes P (problems solvable in polynomial time) and NP (problems solvable in non-deterministic polynomial time) were defined, and one of the most challenging scientific quests of our days arose: whether P = NP. This still open question has implications not only in computer science, mathematics and physics, but also in biology, sociology and economics, and it can be seen as a direct consequence of Turing’s way of looking through the algorithmic lens at different disciplines to discover how pervasive computation is.
Downloads
References
Aaronson, S. (2008). "The limits of quantum computers". Scientific American, 289, pp. 62-69. http://dx.doi.org/10.1038/scientificamerican0308-62
Aaronson, S.; Kuperberg, G. and Granade, C. Complexity Zoo. http://qwiki.stanford.edu/index.php/Complexity_Zoo.
Agrawal, M.; Kayal, N. and Saxena, N. (2002). "Primes is in P". Annals of Mathematics, 2, pp. 781-793.
Arora, S. and Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press. http://dx.doi.org/10.1017/CBO9780511804090
Arora, S.; Lund, C.; Motwani, R.; Sudan, M. and Szegedy, M. (1998). "Proof verification and the hardness of approximation problems". Journal of the ACM, 45 (3), pp. 501-555. http://dx.doi.org/10.1145/278298.278306
Arora, S. and Safra, S. (1998). "Probabilistic checking of proofs: A new characterization of NP". Journal of the ACM, 45 (1), pp. 70-122. http://dx.doi.org/10.1145/273865.273901
Babai, L. (1985). "Trading group theory for randomness". In Proc. 17th. ACM Symposium on the Theory of Computing, pages 421-429.
Bernstein, E. and Vazirani, U. V. (1997). "Quantum complexity theory". SIAM Journal Computing, 26 (5), pp. 1411-1473. http://dx.doi.org/10.1137/S0097539796300921
Brucker, P. (2006). Scheduling Algorithms. Springer, fifth edition.
Cook, S. (1971). "The complexity of theorem-proving procedures". In 3rd. ACM Symposium on the Theory of Computing, pages 151-158.
Cormen, T. H.; Leiserson, C.; Rivest, R. and Stein, C. (2001). Introduction to Algorithms. The MIT Press, 3 edition.
Crescenzi, P. and Kann, V. (2012). A compendium of NP optimization problems.
Dasgupta, S.; Papadimitriou, C. and Vazirani, U. (2008). Algorithms. McGraw-Hill.
Davis, M. (2000). The universal computer: the road from Leibniz to Turing. Norton.
Díaz, J.; Kirousis, L.; Mitsche, D. and Pérez, X. (2009). "On the satisfiability threshold of formulae with three literals per clause". Theoretical Computer Science, 410, pp. 2920-2934. http://dx.doi.org/10.1016/j.tcs.2009.02.020
Doxiadis, A.; Papadimitriou, C.; Papadatos, A. and di Donna, A. (2009). LOGICOMIX: an epic search for truth. Bloomsbury.
Easley, D. and Kleinberg, J. (2010). Networks, Crowds and Markets. Reasoning about a highly connected world. Cambridge University Press. http://dx.doi.org/10.1017/CBO9780511761942
Edmonds, J. (1965). "Paths, trees, and flowers". Canad. J. Math., 17, pp. 449-467. http://dx.doi.org/10.4153/CJM-1965-045-4
Fama, E. (1965). "The behavior of stockmarket prices". The Journal of Business, 38 (1), pp. 34-105. http://dx.doi.org/10.1086/294743
Feigue, U.; Goldwasser, S.; Lovasz, L.; Safra, S. and Szegedy, M. (1996). "Interactive proofs and the hardness of approximating cliques". Journal of the ACM, 43 (2), pp. 268-292. http://dx.doi.org/10.1145/226643.226652
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman.
Glynn, D. G. (2010). "The permanent of a square matrix". European J. of Combinatorics, 31 (7), pp. 1887-1891. http://dx.doi.org/10.1016/j.ejc.2010.01.010
Goldreich, O.; Micali, S. and Wigderson, A. (1991). "Proofs that yield nothing but their validity or all languages in NP have Zero-Knowledge Proof Systems". Journal of the ACM, 38 (1), pp. 691-729.
Goldwasser, S.; Micali, S. and Rackoff, C. (1989). "The knowledge complexity of interactive proof systems". SIAM J. Computing, 18 (1), pp. 186-208. http://dx.doi.org/10.1137/0218012
Graham, R. (1966). "Bounds for certain multiprocessing anomalies". Bell System Technology Journal, 45, pp. 1563-1581. http://dx.doi.org/10.1002/j.1538-7305.1966.tb01709.x
Hajiaghayi, M. T. and Sorkin, G. (2003). The satisfiability threshold of random 3-SAT is at least 3.52. Technical report, IBM Research Report.
Hartmanis, J. and Steam, R. (1965). "On the computational complexity of algorithms". Transactions of the American Mathematical Society, 117, pp. 285-306. http://dx.doi.org/10.1090/S0002-9947-1965-0170805-7
Impagliazzo, R. and Wigderson, A. (1997). "P = BPP if E requires exponential circuits: Derandomizing the XOR lemma". In Proceedings of tTwenty-Ninth Annual ACM Symposium on the Theory of Computing, pages 220-229. http://dx.doi.org/10.1145/258533.258590
Johnson, D. J. (1974). Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9, 256-278. http://dx.doi.org/10.1016/S0022-0000(74)80044-9
Johnson, D. S. (1992). "The NP-completeness column. The tale of the second prover". Journal of Algorithms, 13 (3), pp. 502-524. http://dx.doi.org/10.1016/0196-6774(92)90052-E
Kaporis, A. C.; Kirousis, L. and Lalas, E. G. (2006). "The probabilistic analysis of a greedy satisfiability algorithm". Random Struct. Algorithms, 28 (4), pp. 444-480. http://dx.doi.org/10.1002/rsa.20104
Karp, R. M. (1972). "Reducibility among combinatorial problems". In R. E. Miller and J. W. Thatcher (eds.), Complexity of Computer Computations, pp. 85-104. NY: Plenum Press. http://dx.doi.org/10.1007/978-1-4684-2001-2_9
Levin, L. (1973). "Universal sequential search problems". Probl. Peredachi Inf., 9, pp. 115-116.
Lipton, R. Godel's lost letter and P = NP. http://rjlipton.wordpress.com.
Lipton, R. (2010). The P=NP Question and Godel's Lost Letter. Springer. http://dx.doi.org/10.1007/978-1-4419-7155-5
Maymin, P. (2011). "Markets are efficient if and only if P=NP". Algorithmic Finance, 1, pp. 1-11.
Mezard, M.; Parisi, G. and Zecchina, R. (2002). "Analytic and algorithmic solution of random satisfiability problems". Science, 297 (812).
Mezard, M. and Zecchina, R. (2002). "The random k-satisfiability problem: from an analytic solution to an efficient algorithm". Physics Review, E 66-056126. http://dx.doi.org/10.1103/PhysRevE.66.056126
Michalewicz, Z. and Fogel, D. (1998). How to solve it: Modern Heuristics. Springer.
Mitchell, D.; Selman, B. and Levesque, H. (1992). "Hard and easy distributions of sat problems". In Proceedings of the 10th. National Conference on Artificial Intelligence (AAAI), pp. 459-465.
Moore, C. and Mertens, S. (2011). The Nature of Computation. Oxford University Press. Nissan, N. (2004). John Nash's letter to the NSA. http://agtb.wordpress.com/2012/02/17/john-nashs-letter-tothe-nsa/, February 17.
Pratt, V. R. (1975). "Every prime has a succinct certificate". SIAM J. Comput., 4 (3), pp. 214-220. http://dx.doi.org/10.1137/0204018
Quisquater, J.-J.; Quisquater, M.; Quisquater, M.; Quisquater, M.; Guillou, L. C.; Guillou, M. A.; Guillou, G.; Guillou, A.; Guillou, G.; Guillou, S. and Berson, T. A. (1989). "How to explain zero-knowledge protocols to your children". In G. Brassard, editor, CRYPTO-89, volume 435 of Lecture Notes in Computer Science, pp. 628-631. Springer.
Shamir, A. (1992). "IP = PSPACE". Journal of the ACM, 39 (4), pp. 869-877. http://dx.doi.org/10.1145/146585.146609
Shor, P. W. (1997). "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer". SIAM J. Comput., 26 (5), pp. 1484-1509. http://dx.doi.org/10.1137/S0097539795293172
Singh, S. (2000). The Code Book. Anchor Books. Trakhtenbrot, B. (1984). "A survey of russian approaches to perebor (brute-force searches) algorithms". Annals of the History of Computing, 6 (4), pp. 384-400. http://dx.doi.org/10.1109/MAHC.1984.10036
Turing, A. M. (1939). Systems of logic based on ordinals. Proceedings of the London Mathematical Society-2, 45, pp. 161-228. http://dx.doi.org/10.1112/plms/s2-45.1.161
Valiant, L. G. (1979). "The complexity of enumeration and reliability problems". SIAM J on Computing, 8, pp. 410-421. http://dx.doi.org/10.1137/0208032
Williamson, D. and Smoys, D. (2010). The Design of Approximation Algorithms. Cambridge University Press. Woeginger, G. The P vs. NP page. http://www.win.tue.nl/gwoegi/P-versus-NP.htm.
Wolf, W. (2011). Modern VLSI Design. Prentice-Hall, fourth edition.
Published
How to Cite
Issue
Section
License
Copyright (c) 2013 Consejo Superior de Investigaciones Científicas (CSIC)
This work is licensed under a Creative Commons Attribution 4.0 International License.
© CSIC. Manuscripts published in both the printed and online versions of this Journal are the property of Consejo Superior de Investigaciones Científicas, and quoting this source is a requirement for any partial or full reproduction.All contents of this electronic edition, except where otherwise noted, are distributed under a “Creative Commons Attribution 4.0 International” (CC BY 4.0) License. You may read here the basic information and the legal text of the license. The indication of the CC BY 4.0 License must be expressly stated in this way when necessary.
Self-archiving in repositories, personal webpages or similar, of any version other than the published by the Editor, is not allowed.
