---

---

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 complejidad^1,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 Cook³.

Fuente: Quanta Magazine⁴.

P
NP

Referencias

1. «Theory of Computation«, Wikipedia, web. Visited: 2018.09.26. URL: https://en.wikipedia.org/wiki/Theory_of_computation.
2. 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.
3. 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
4. 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/.
5. https://www.interviewcake.com/article/python/big-o-notation-time-and-space-complexity
6. 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.
7. «Big O Notation«, MIT, «Introduction to Computers and Programming» web site. Visited: 2023.07.20. URL: https://web.mit.edu/16.070/www/lecture/big_o.pdf.

---

El contenido de este sitio puede ser copiado y reproducido libremente, siempre que no se altere y se cite su origen. Marcas y productos registrados se citan por referencia y sin fines de lucro ni dolo. Todas las opiniones son a título personal del o de los autores de estas y, salvo que se exprese de otro modo, deben considerarse como registro y expresión de la experiencia de uso de aquello de lo que se trata. Para conocer más sobre la posición de privacidad y responsabilidad respecto de lo que se presenta en este sitio web y de cómo se ha obtenido, consulte la declaración correspondiente.