La lente algorítmica de Turing: de la computabilidad a la teoría de la complejidad


  • Josep Díaz Llenguatges i Sistemes Informàtics, UPC
  • Carme Torras Institut de Robòtica i Informàtica Industrial, CSIC-UPC


Palabras clave:

Complejidad computacional, el problema de calcular la permanente de una matriz, problemas P y NP, demostraciones interactivas y holográficas


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.


Los datos de descargas todavía no están disponibles.


Aaronson, S. (2008). "The limits of quantum computers". Scientific American, 289, pp. 62-69.

Aaronson, S.; Kuperberg, G. and Granade, C. 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.

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.

Arora, S. and Safra, S. (1998). "Probabilistic checking of proofs: A new characterization of NP". Journal of the ACM, 45 (1), pp. 70-122.

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.

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.

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.

Edmonds, J. (1965). "Paths, trees, and flowers". Canad. J. Math., 17, pp. 449-467.

Fama, E. (1965). "The behavior of stockmarket prices". The Journal of Business, 38 (1), pp. 34-105.

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.

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.

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.

Graham, R. (1966). "Bounds for certain multiprocessing anomalies". Bell System Technology Journal, 45, pp. 1563-1581.

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.

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.

Johnson, D. J. (1974). Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9, 256-278.

Johnson, D. S. (1992). "The NP-completeness column. The tale of the second prover". Journal of Algorithms, 13 (3), pp. 502-524.

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.

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.

Levin, L. (1973). "Universal sequential search problems". Probl. Peredachi Inf., 9, pp. 115-116.

Lipton, R. Godel's lost letter and P = NP.

Lipton, R. (2010). The P=NP Question and Godel's Lost Letter. Springer.

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.

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., February 17.

Pratt, V. R. (1975). "Every prime has a succinct certificate". SIAM J. Comput., 4 (3), pp. 214-220.

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.

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.

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.

Turing, A. M. (1939). Systems of logic based on ordinals. Proceedings of the London Mathematical Society-2, 45, pp. 161-228.

Valiant, L. G. (1979). "The complexity of enumeration and reliability problems". SIAM J on Computing, 8, pp. 410-421.

Williamson, D. and Smoys, D. (2010). The Design of Approximation Algorithms. Cambridge University Press. Woeginger, G. The P vs. NP page.

Wolf, W. (2011). Modern VLSI Design. Prentice-Hall, fourth edition.



Cómo citar

Díaz, J., & Torras, C. (2013). La lente algorítmica de Turing: de la computabilidad a la teoría de la complejidad. Arbor, 189(764), a080.