PROBLEMAS P Y NP EN LA COMPLEJIDAD COMPUTACIONAL

 AUTOR:

• LUIS ANGEL GONZALES ESQUIVEL

PALABRAS CLAVES: Algoritmo, Máquina de Turing, complejidad computacional, determinismo, no determinismo, lógica clásica, lógica cuántica, interdisciplinariedad.

RESUMEN

Este documento de tesis tiene el objetivo de sustentar por qué un problema de tipo no polinomial (NP), dentro de la lógica de la computación clásica, se puede convertir en un problema de tipo polinomial (P) dentro de la lógica de la computación cuántica. Para ello, se busca relacionar la complejidad computacional con la lógica cuántica; se sabe que la complejidad computacional trata de los problemas P vs NP, pero dentro de la lógica clásica. Se sabe que la complejidad computacional está diseñada dentro de la lógica clásica, pero no hay todavía, un diseño de la complejidad computacional dentro de la lógica cuántica, debido a que la lógica cuántica es una ciencia en pleno desarrollo, todavía no hay computadores cuánticos capaces de superar a los computadores clásicos, la supremacía cuántica por ahora es algorítmica y teórica. Es necesario desarrollar la complejidad computacional desde las Máquinas de Turing, con la lógica de la computación clásica, los algoritmos computacionales clásicos, el determinismo y la secuencialidad de los computadores clásicos. Se sabe que las Máquinas de Turing son máquinas secuenciales, deterministas, y en la práctica son modelos teóricos de los computadores clásicos. Aunque existen Máquinas de Turing no deterministas a nivel teórico, en la práctica los computadores clásicos son deterministas. Se desarrolla la lógica cuántica dentro de la computación cuántica, con algoritmos cuánticos, el no determinismo y la no secuencialidad. Por último, se compara las características de la lógica clásica frente a la lógica cuántica, encontrándose que la supremacía cuántica se da por las características no deterministas que tiene la computación cuántica, especialmente el paralelismo, la superposición y el entrelazamiento cuántico. En la complejidad computacional clásica, se sabe que los problemas de tipo no polinomial se vuelven polinomiales con algoritmos no deterministas. También es importante la interdisciplinariedad en la biología con el cerebro cuántico, la lingüística, las matemáticas, la física, las telecomunicaciones, la psicología educativa, la didáctica y la informática. 

Texto completo PDF