Ir al contenido

Documat

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

  • Autores: Josep Díaz Cort Árbol académico, Carme Torras Genís Árbol académico
  • Localización: Arbor: Ciencia, pensamiento y cultura, ISSN 0210-1963, Nº 764, 2013
  • Idioma: inglés
  • Enlaces
  • Resumen

    • The decidability question, i.e., whether any mathematical statement could be computationally proven true or false, was raised by Hilbert and remained open until Turing answered it in the negative. Then, most efforts in theoretical computer science turned to complexity theory and the need to classify decidable problems according to their difficulty. Among others, the classes P (problems solvable in polynomial time) and NP (problems solvable in non-deterministic polynomial time) were defined, and one of the most challenging scientific quests of our days arose:

      whether P = NP. This still open question has implications not only in computer science, mathematics and physics, but also in biology, sociology and economics, and it can be seen as a direct consequence of Turing�s way of looking through the algorithmic lens at different disciplines to discover how pervasive computation is.

  • Referencias bibliográficas
    • 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"....
    • Arora, S. and Safra, S. (1998). "Probabilistic checking of proofs: A new characterization of NP". Journal of the ACM, 45 (1), pp....
    • 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"....
    • 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"....
    • 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...
    • Goldwasser, S.; Micali, S. and Rackoff, C. (1989). "The knowledge complexity of interactive proof systems". SIAM J. Computing, 18...
    • 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,...
    • Impagliazzo, R. and Wigderson, A. (1997). "P = BPP if E requires exponential circuits: Derandomizing the XOR lemma". In Proceedings...
    • 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....
    • Karp, R. M. (1972). "Reducibility among combinatorial problems". In R. E. Miller and J. W. Thatcher (eds.), Complexity of Computer...
    • 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...
    • Mezard, M. and Zecchina, R. (2002). "The random k-satisfiability problem: from an analytic solution to an efficient algorithm". Physics...
    • 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...
    • Moore, C. and Mertens, S. (2011). The Nature of Computation. Oxford University Press. Nissan, N. (2004). John Nash's letter to the NSA....
    • 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.;...
    • 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.,...
    • Singh, S. (2000). The Code Book. Anchor Books. Trakhtenbrot, B. (1984). "A survey of russian approaches to perebor (brute-force searches)...
    • 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....
    • Wolf, W. (2011). Modern VLSI Design. Prentice-Hall, fourth edition.
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno