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

Autores/as

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

DOI:

https://doi.org/10.3989/arbor.2013.764n6003

Palabras clave:

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

Resumen


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

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

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

2013-12-30

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. https://doi.org/10.3989/arbor.2013.764n6003

Número

Sección

Artículos