Um problema fundamental na investigação: Os problemas P contra NP
DOI:
https://doi.org/10.22335/rlct.v4i2.186Palavras-chave:
logica, matemáticas, complexidade, metodologia da investigação, complexidade algorítmica, complexidade computacionalResumo
O problema mais difícil e apaixonante em qualquer investigação consiste na formulação ou identificação do problema. O método da investigação cientista não tinha sido abordado suficientemente neste tema, quanto menos se falar de fenômenos, contextos, problemas ou sistemas complexos. Este texto apresenta, discute e reflexiona a respeito dos problemas P contra NP dirigindo uma olhada até o espaço da investigação e a sua metodologia. Alguns dos eixos da reflexão que resultam são aqueles da complexidade algorítmica e da complexidade computacional de um problema. Ao final se sugere a tese do trabalho com problemas em termos de conjuntos e espaços de solução em relação direita com a classe de problemas P=! NP.
Downloads
Referências
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
Publicado
Edição
Seção
Licença
Esta revista proporciona acesso livre e imediato ao seu conteúdo (https://creativecommons.org/licenses/by/4.0/legalcode#languages), sob o princípio de que fazer disponível gratuitamente pesquisa ao público apoia a um maior intercâmbio de conhecimento global. Isto significa que os autores transferem o Copyright à revista, para que possam realizar cópias e distribuição dos conteúdos por qualquer meio, sempre que se mantenha o reconhecimento de seus autores, não faça uso comercial das obras e não realize nenhuma modificação delas.
