 |
La teoría detrás de la complejidad computacional comenzó a interesarme mientras estudiaba la licenciatura. En aquel entonces el tema se resumía al problema de P versus NP. Hoy, podemos ver como se ha expandido enormemente y abarca desde el cómputo tradicional hasta el cuántico. |
Índice
Introducción
En teoría de la computación, el tema de la complejidad computacional es una rama que se centra en la clasificación de problemas de acuerdo con la dificultad inherente al procedimiento de la solución (o equivalentes) más eficiente, y la relación entre dichas clases de complejidad1,2. La teoría de la complejidad computacional trata de clasificar los problemas que pueden, o no pueden ser resueltos con una cantidad determinada de recursos.
Un problema se cataloga como «inherentemente difícil» si su solución requiere de una cantidad significativa de recursos o tiempo. La formalización del problema y su solución se hace introduciendo modelos de cómputo.
Dos objetivos importantes de la teoría son:
- Determinar los límites prácticos de qué es lo que se puede hacer en una computadora y qué no.
- La cantidad de recursos físicos o tiempo que requerirá hallar una solución a partir de un determinado número de insumos de entrada o de operaciones para calcular la respuesta.
Relacionada con el tema está el análisis de algoritmos y la teoría de la computabilidad. El primero se dedica a determinar el algoritmo (procedimiento de solución) para resolver un problema, su eficiencia y validez. La segunda se revisa la existencia y relación de todos los posibles algoritmos que pudieran ser usados para resolver el mismo problema, más la imposición de restricciones sobre los recursos para hacerlo.
Antecedentes
Línea de tiempo
1930
Kurt Gödel
Alan Turing
Emile Post
Alonzo Church
1940
Claude Shannon
1950
1960
Aparecen los primeros artículos tratando explícitamente el tema del costo computacional. Definición del tiempo polinomial (Cobhams, Edmonds, Peterson).
Jerarquías de tiempo, teoremas de aceleración, medidas abstractas de complejidad
1970
Formulación del a pregunta P=NP, NP-Completo
Clases
Lejos han quedado los días de 1971 en los que sólo se percibía dos grandes universos P y NP, como inicialmente introdujo Stephen Cook3.
Fuente: Quanta Magazine4.
P
NP
Referencias
- «Theory of Computation«, Wikipedia, web. Visited: 2018.09.26. URL: https://en.wikipedia.org/wiki/Theory_of_computation.
- Teoría de la computación«, Wikipedia, web. Visitada: 2018.09.26. URL: https://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_computación.
- Stephen Cook, «The complexity of theorem proving procedures». Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971. pp. 151–158. URL: https://dl.acm.org/ft_gateway.cfm?id=805047&ftid=53543&dwn=1&CFID=17342762&CFTOKEN=55f483b030ac481b-F51A26FE-D5D3-EDDB-3167E0D793C2F062
- Kevin Harnett, «A Short Guide to Hard Problems«, Quanta Magazine, web. Published: 2018.07.16; Visited: 2018.09.26. URL: https://www.quantamagazine.org/a-short-guide-to-hard-problems-20180716/.
- https://www.interviewcake.com/article/python/big-o-notation-time-and-space-complexity
- G. J. Woeginger, «The P versus NP page«, web. Reviewed: 2016.09.16; visited: 2020.05.18. URL: https://www.win.tue.nl/~gwoegi/P-versus-NP.htm.
|
© Todos los derechos reservados. Dr. Eduardo René Rodríguez Ávila |
Creación: 2018.09.26 Última actualización: 2020.05.18 |
|||
| El contenido de este sitio puede ser copiado y reproducido libremente mientras no sea alterado y se cite su origen. Marcas y productos registrados son citados por referencia y sin fines de lucro o dolo. Todas las opiniones son a título personal del o los autores de éstas y, salvo sea expresado de otro modo, deben considerarse como registro y expresión de la experiencia de uso de aquello que es tratado. Para conocer más sobre la posición de privacidad y responsabilidad de lo que se presenta en este sitio web y como ha sido obtenido, consulte la declaración al respecto. | |||||
Dr. Edu 