Teoría de la complejidad computacional
La teoría de la complejidad computacional se enfoca en clasificar los problemas computacionales de acuerdo con su uso de recursos y relacionar estas clases entre sí. Un problema computacional es una tarea resuelta por una computadora. Un problema de cálculo se puede resolver mediante la aplicación mecánica de pasos matemáticos, como un algoritmo .
Un problema se considera intrínsecamente difícil si su solución requiere recursos importantes, sea cual sea el algoritmo utilizado. La teoría formaliza esta intuición, al introducir modelos matemáticos de computación para estudiar estos problemas y cuantificar su complejidad computacional , es decir, la cantidad de recursos necesarios para resolverlos, como el tiempo y el almacenamiento. También se utilizan otras medidas de complejidad, como la cantidad de comunicación (utilizada en la complejidad de la comunicación ), el número de puertas en un circuito (utilizado en la complejidad del circuito ) y el número de procesadores (utilizado en la computación en paralelo).). Uno de los roles de la teoría de la complejidad computacional es determinar los límites prácticos de lo que las computadoras pueden y no pueden hacer. El problema P versus NP , uno de los siete problemas del premio Millennium , está dedicado al campo de la complejidad computacional. [1]
Los campos estrechamente relacionados en la informática teórica son el análisis de algoritmos y la teoría de la computabilidad.. Una distinción clave entre el análisis de algoritmos y la teoría de la complejidad computacional es que el primero se dedica a analizar la cantidad de recursos que necesita un algoritmo en particular para resolver un problema, mientras que el segundo hace una pregunta más general sobre todos los algoritmos posibles que podrían usarse para resolver el mismo problema. Más precisamente, la teoría de la complejidad computacional intenta clasificar los problemas que pueden o no pueden resolverse con recursos apropiadamente restringidos. A su vez, imponer restricciones a los recursos disponibles es lo que distingue la complejidad computacional de la teoría de la computabilidad: esta última teoría pregunta qué tipos de problemas pueden, en principio, resolverse algorítmicamente.
Un problema computacional puede verse como una colección infinita de instancias junto con un conjunto (posiblemente vacío) de soluciones para cada instancia. La cadena de entrada para un problema de cálculo se denomina instancia de problema y no debe confundirse con el problema en sí. En la teoría de la complejidad computacional, un problema se refiere a la pregunta abstracta que se debe resolver. Por el contrario, un ejemplo de este problema es un enunciado bastante concreto, que puede servir como entrada para un problema de decisión. Por ejemplo, considere el problema de las pruebas de primalidad . La instancia es un número (por ejemplo, 15) y la solución es "sí" si el número es primo y "no" en caso contrario (en este caso, 15 no es primo y la respuesta es "no"). Dicho de otra manera,elinstancia es una entrada particular al problema, y la solución es la salida correspondiente a la entrada dada.
Para resaltar aún más la diferencia entre un problema y una instancia, considere la siguiente instancia de la versión de decisión del problema del viajante de comercio : ¿Hay una ruta de como máximo 2000 kilómetros que pase por las 15 ciudades más grandes de Alemania? La respuesta cuantitativa a esta instancia particular del problema es de poca utilidad para resolver otras instancias del problema, como pedir un viaje de ida y vuelta a través de todos los sitios en Milán cuya longitud total sea como máximo de 10 km. Por esta razón, la teoría de la complejidad aborda problemas computacionales y no instancias de problemas particulares.
Al considerar los problemas de cálculo, una instancia de problema es una cadena sobre un alfabeto . Por lo general, se considera que el alfabeto es el alfabeto binario (es decir, el conjunto {0,1}) y, por lo tanto, las cadenas son cadenas de bits . Al igual que en una computadora del mundo real , los objetos matemáticos que no sean cadenas de bits deben codificarse adecuadamente. Por ejemplo, los números enteros se pueden representar en notación binaria y los gráficos se pueden codificar directamente a través de sus matrices de adyacencia o codificando sus listas de adyacencia en binario.
