Notas sobre complejidad computacional
DOI:
https://doi.org/10.59471/raia2024210Palabras clave:
complejidad computacional, P VS NP, algoritmoResumen
Dos aspectos centrales del proyecto en curso del CAETI, de creacion de un ambiente de desarrollo de software basado en conceptos avanzados de modularizacion y sintesis de comportamiento, son la correctitud y la eficiencia. En relación al primer aspecto, en artículos anteriores describimos la verificación axiomática de programas. En este artículo nos enfocamos en la eficiencia, presentando una serie de notas que cubren sucintamente temas relevantes de la complejidad computacional, área de la teoría de la computación que estudia la dificultad inherente de los problemas. Se tratan los paradigmas determinístico, probabilístico y cuántico, incluyendo elementos vinculados con la criptografía, las pruebas y la desaleatorización de los algoritmos. El material integra los contenidos de la asignatura Métodos Formales en la Ingeniería de Software, que se dicta en el Doctorado en Informática de la Facultad de Tecnología Informática de la UAI.
Referencias
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.
Descargas
Publicado
Número
Sección
Licencia
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial 4.0.
