Notes on Computational Complexity
DOI:
https://doi.org/10.59471/raia2024210Keywords:
computational complexity, P VS NP, algorithmAbstract
Two central aspects of the ongoing CAETI project, to create a software development environment based on advanced concepts of modularization and behavioral synthesis, are correctness and efficiency. Regarding the first aspect, in previous articles we described the axiomatic verification of programas. In this article we focus on efficiency, presenting a series of notes that succinctly cover relevant topics in computational complexity, an area of computational theory that studies the inherent difficulty of problems. The deterministic, probabilistic and quantum paradigms are discussed, including elements related to cryptography, proofs and the derandomization of algorithms. The material integrates the contents of the course Formal Methods in Software Engineering, which es taught in the Doctorate in Computer Science of the Faculty of Computer Technology of the UAI.
Downloads
References
Aaronson, S. (2013a). Quantum computing since Democritus. Cambridge University Press.
Aaronson, S. (2013b). Why Philosophers Should Care About Computational Complexity. En Computability: Gödel, Turing, Church, and Beyond, MIT Press, 2013.
Agrawal, M., Kayal, N. y Saxena, N. (2004). Primes is in P. Annals of Mathematics, 160(2), 781-793.
Arora, S. y Barak, B. (2009). Computational complexity: a modern approach. Cambridge University Press.
Babai, L. (2016). Graph isomorphism in quasipolynomial time. STOC ‘16, Proc. of the 48th annual ACM Symp. on Theory of Computing, 684-697.
Bovet, D. y Crescenzi, P. (1994). Introduction to the theory of complexity. Prentice-Hall.
Church, A. (1936a). An unsolvable problem of elementary number theory. American Journal of Mathematics, 58(2), 345-363.
Church, A. (1936b). A note on Entscheidungsproblem. The Journal of Symbolic Logic, (1)1, 40-41.
Cook, S. (1971). The complexity of theorem-proving procedures. Proc. of the 3rd IEEE Symp. on the Foundations of Computer Science, 151-158.
Gasarch, W. (2002). The P =? NP poll. ACM SIGACT News, 33(2), 34-47.
Gasarch, W. (2012). The second P =? NP poll. ACM SIGACT News, 43(2), 53-77.
Gasarch, W. (2019). The third P =? NP poll. ACM SIGACT News, 50(1), 38-59.
Gödel, K. (1931). Über formal unentscheidbare Sätze der Principia mathematica und verwandter Systeme I. Monatshefte fur Math, Und Physik, 38, 173-198. En español: Sobre sentencias formalmente indecidibles de Principia Mathematica y sistemas afines. Obras Completas de Kurt
Goldreich, O. (2008). Computational complexity: a conceptual perspective. Cambridge University Press.
Grover, L. (1996). A fast quantum mechanical algorithm for database search. STOC, 212-219, ACM.
Immerman, N. (1988). Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17, 935-938.
Ladner, R. (1975). On the structure of polynomial-time reducibility. JACM, 22, 155-171.
Levin, L. (1973). Universal’nyie perebornyie zadachi. Problemy Peredachi Informatsii, 9, 115,116. En inglés: Universal search problems. Problems of Information Transmission, 9, 265-266.
Moore. C. y Mertens, S. (2011). The nature of computation. Oxford University Press.
Nielsen, M. y Chuang, I. (2010). Quantum computation and quantum information. Cambridge University Press.
Papadimitriou, C. (1994). Computational complexity. Addison-Wesley.
Rabin, M. (1980). A probabilistic algorithm for testing primality. Journal of Number Theory, 12(1), 128-138.
Reingold, O. (2005). Undirected ST-connectivity in log-space. STOC, 376-385, ACM.
Rosenfeld, R. (2024). Computabilidad y complejidad computacional (versión preliminar). EDULP.
Rosenfeld, R. e Irazábal, J. (2010). Teoría de la computación y verificación de programas. EDULP, McGraw-Hill.
Rosenfeld, R e Irazábal, J. (2013). Computablidad, complejidad computacional y verificación de programas. EDULP.
Savitch, W. (1970). Relationship between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4, 177-192.
Shor, P. (1994). Algorithms for quantum computation: discrete logarithms and factoring. Proc. 35th Annual Symp. on Foundations of Computer Science, IEEE Press.
Solovay, R. y Strassen,V. (1977). A fast Monte-Carlo test for primality. SIAM Journal on Computing, 6, 84-85.
Stockmeyer, L. y Meyer, A. (1973). Word problems requiring exponential time. Proc. 5th ACM Symp. on the Theory of Computing, 1-9.
Turing, A. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proc. London Mathematical Society, 2(42), 230-265.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
