¿Qué es la teoría de la complejidad computacional?
La teoría de la complejidad computacional es un área de las matemáticas y la informática que se ocupa de los recursos necesarios para resolver problemas en un sistema informático. Hay varias técnicas disponibles para determinar los requisitos de recursos de un problema. Algunos problemas pueden no ser viables en los sistemas informáticos existentes debido a sus demandas de recursos. Los investigadores clasifican los problemas por dificultad y pueden dividir los cálculos en problemas de polinomios (P) versus problemas de polinomios (NP) no terminales.
Resolver un cálculo requiere recursos como tiempo, espacio de almacenamiento y hardware. Un sistema informático puede tener limitaciones que hacen que un problema sea funcionalmente imposible de resolver porque no tiene los recursos disponibles. A medida que la tecnología informática mejora, un problema que antes no se podía resolver podría resolverse con la ayuda de nuevas tecnologías e investigaciones en el campo de la teoría de la complejidad computacional. La capacidad de solución de un problema no está necesariamente determinada por su complejidad, sino por los algoritmos utilizados para resolverlo.
En la teoría de la complejidad computacional, un problema P es uno que puede resolverse en tiempo polinómico con un algoritmo directo. Todavía puede requerir recursos sustanciales, pero es solucionable y comprobable por computadora. Se podría pensar que tales problemas se pueden resolver rápidamente, siempre y cuando una computadora tenga los recursos disponibles para manejar los cálculos necesarios.
Los problemas de NP son más complejos. No es posible aplicar un solo algoritmo, y puede ser necesario usar opciones más avanzadas, como máquinas paralelas de Turing que pueden explorar varias opciones. El problema puede resolverse de esta manera, pero requerirá sustancialmente más recursos. Tales problemas podrían ser más fáciles para los operadores humanos que son capaces de pensar lógicamente avanzado, porque el punto de inflexión es a menudo uno de lógica en lugar de pura dificultad de cálculo. El problema del vendedor ambulante, en el que el objetivo es encontrar la ruta más eficiente entre varias ciudades a lo largo de una ruta, es un ejemplo clásico de un problema de NP en la teoría de la complejidad computacional.
La clasificación de los problemas P versus NP a través de la teoría de la complejidad computacional puede ser una tarea compleja, y los problemas pueden cambiar de un lado a otro. Un pequeño conjunto de problemas computacionales no encaja perfectamente en ninguna de las categorías y a veces se clasifican como ninguno para reflejar esto. Eventualmente podría ser posible desarrollar un algoritmo para resolver un problema de NP, y en algunos casos, podría aplicarse a otros problemas que tienen una estructura similar. En otros, sin embargo, puede ser específico del problema. El proceso de explorar tales programas y desarrollar enfoques para resolverlos es un área importante de las matemáticas y la informática que contribuye al desarrollo de sistemas informáticos avanzados y de alta potencia.