La lente algorítmica de Turing: de la computabilidad a la teoría de la complejidad
DOI:
https://doi.org/10.3989/arbor.2013.764n6003Palabras clave:
Complejidad computacional, el problema de calcular la permanente de una matriz, problemas P y NP, demostraciones interactivas y holográficasResumen
La cuestión de la decidibilidad, es decir, si es posible demostrar computacionalmente que una expresión matemática es verdadera o falsa, fue planteada por Hilbert y permaneció abierta hasta que Turing la respondió de forma negativa. Establecida la no-decidibilidad de las matemáticas, los esfuerzos en informática teórica se centraron en el estudio de la complejidad computacional de los problemas decidibles. En este artículo presentamos una breve introducción a las clases P (problemas resolubles en tiempo polinómico) y NP (problemas resolubles de manera no determinista en tiempo polinómico), al tiempo que exponemos la dificultad de establecer si P = NP y las consecuencias que se derivarían de que ambas clases de problemas fueran iguales. Esta cuestión tiene implicaciones no solo en los campos de la informática, las matemáticas y la física, sino también para la biología, la sociología y la economía. La idea seminal del estudio de la complejidad computacional es consecuencia directa del modo en que Turing abordaba problemas en diferentes ámbitos mediante lo que hoy se denomina la lupa algorítmica. El artículo finaliza con una breve exposición de algunos de los temas de investigación más actuales: transición de fase en problemas NP, y demostraciones holográficas, donde se trata de convencer a un adversario de que una demostración es correcta sin revelar ninguna idea de la demostración.
Descargas
Citas
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.
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2013 Consejo Superior de Investigaciones Científicas (CSIC)
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
© CSIC. Los originales publicados en las ediciones impresa y electrónica de esta Revista son propiedad del Consejo Superior de Investigaciones Científicas, siendo necesario citar la procedencia en cualquier reproducción parcial o total.Salvo indicación contraria, todos los contenidos de la edición electrónica se distribuyen bajo una licencia de uso y distribución “Creative Commons Reconocimiento 4.0 Internacional ” (CC BY 4.0). Puede consultar desde aquí la versión informativa y el texto legal de la licencia. Esta circunstancia ha de hacerse constar expresamente de esta forma cuando sea necesario.
No se autoriza el depósito en repositorios, páginas web personales o similares de cualquier otra versión distinta a la publicada por el editor.
