Un problema fundamental en la investigación: Los problemas P vs. NP
DOI:
https://doi.org/10.22335/rlct.v4i2.186Palabras clave:
lógica, matemáticas, complejidad, metodología de la investigación, complejidad algorítmica, complejidad computacionalResumen
Lo más difícil y apasionante en cualquier investigación consiste en la formulación o identificación del problema. La metodología de la investigación científica no ha abordado suficientemente este tema, y tanto menos cuando se trata de fenómenos, contextos, problemas o sistemas complejos. Este texto presenta, discute y reflexiona acerca de los problemas P vs. NP direccionando la mirada hacia el espacio de la investigación y su metodología. Algunos de los ejes de reflexión que resultan son los de la complejidad algorítmica y la complejidad computacional de un problema. Al final se sugiere la tesis del trabajo con problemas en términos de conjuntos y espacios de solución en relación directa con la clase problemas P =! NP.
Descargas
Referencias
Carlson, J., Jaffe, A., and Wils, A. (Eds.) (2006). The Millenium Problems. Cambridge, MA: Clay Mathematics Institute-American Mathematical Society.
Cook, S. (1971). "The complexity of theorem-proving procedures", en: Conference Record of Third Annual ACM Symposium on Theory of Computing, New York: ACM, págs. 151-158.
Deolalikar, V. (2010). P ≠NP . HP Research Labs, Palo Alto, California.
Devlin, K. (2002). The Millenium Problems. The Sev en Greatest Unsolved Mathematical Puzzles of Our Time. New York: Basic Books.
Gray, D. (2005). El reto de Hilbert. Los 23 problemas que desafiaron a la matemática. Barcelona: Crítica (original, 2000, Oxford University Press).
Karp, R. M. (1972). Reducibility among combinato rial problems , en: Complexity of Computer Computations, Miller, R. E., and Thatcher, J. W., (eds.), New York: Plenum Press, págs. 85-103.
Kuhn, Th. (1996). Estructura de las revoluciones cien tíficas . México: F. C. E.
Levin, L. (1973). Universal Search Problems (en ruso), Problemy Peredachi Informatsii 9 [Problemas de información de la comunicación, C. E. M.], págs. 265266. Traducción al inglés en. Trakhtenbrot, B. A., A Survey of Russian Approcahes to Perebor (bruteforce search) algorithms, en: Annals of History of Computing (1984), págs. 384-400.
Lipton, R. J., (2010). The P = NP Question and Gödels Lost Letter. New York: Springer Verlag.
Maldonado, C. E. (2012a) "¿Qué son las ciencias de la complejidad? Filosofía de la ciencia de la complejidad", en: Maldonado Derivas de complejidad. Funda mentos cientificos y filosóficos, Maldonado, C. E. (Ed.), Bogotá, Ed. Universidad del Rosario, págs. 7-102.
Maldonado, C. E., Gómez Cruz, N. (2012b). "Biological Hypercomputation: A Concept is Introduced", en: 2nd International Conference on Complex Systems, Santa Fe, NM, diciembre (en prensa).
Maldonado, C. E., Gómez-Cruz, N. (2011). "Facing N-P Problems via Artificial Life: A Philosophical Appraisal", en: Kampis, G., Karsai, I., and Szathmáry, E., (Eds.), ECAL 2009, Part II, LNCS 5778, págs. 216-221, Berlin: Springer Verlag.
Polya, G. (1965). Cómo plantear y resolver prob lemas. Madrid: Ed. Trillas.
Wiener, N. (1995). Inventar . Barcelona: Tusquets.
Publicado
Número
Sección
Licencia
Esta revista provee acceso libre e inmediato a su contenido (https://creativecommons.org/licenses/by-nc-nd/4.0/), bajo el principio de hacer disponible gratuitamente la investigación al público y apoyar a un mayor intercambio de conocimiento global.
