A fundamental problem in the research: P vs problems. NP
DOI:
https://doi.org/10.22335/rlct.v4i2.186Keywords:
Logics, mathematics, complexity, methodology in research, algorithmic complexity, computational complexityAbstract
Probably the most difficult and yet enthralling of all troubles concerning research at large concerns the stating of the problem of research. Scientific methodology has not dealt so much with this issue, particularly when the concern is about complex systems, phenomena, contexts, or problems. This paper presents, discusses and reflects upon the problems P vs. NP calling the attention toward the framework of research and its methodology. Some the axes under consideration here are algorithmic complexity and computational complexity within a given problem. At the end the claim is made regarding the work with problems in terms of sets of problems and space solutions corresponding to the set of problems P =! NP.
Downloads
References
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.
Downloads
Published
Issue
Section
License
This journal provides free and immediate access to its content (https://creativecommons.org/licenses/by/4.0/legalcode#languages), under the principle that making research available to the public free of charge supports greater global knowledge exchange. This means that the authors transfer the Copyrights to the journal, so that the material can be copied and distributed by any means, as long as the authors’ recognition is maintained, and the articles are not commercially used or modified in any way.
