Complejidad computacional
Keywords: Complejidad computacional, Algoritmos de ordenamiento, Array, BQP, Búsqueda binaria, Clase de complejidad, Clay Mathematics Institute
La Teoría de la complejidad computacional es la parte de la teoría de la computación que estudia los recursos requeridos durante el cálculo para resolver un problema. Los recursos comúnmente estudiados son el tiempo (número de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (cantidad de memoria utilizada para resolver un problema). Se pueden estudiar igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo. La teoría de la complejidad defiere de la teoría de la computabilidad en que esta última se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello.
Los problemas que tienen una solución con orden de complejidad lineal son los problemas que se resuelven en un tiempo que se relaciona linealmente con su tamaño.
Hoy en día las máquinas resuelven problemas mediante algoritmos que tienen como máximo una complejidad o coste computacional polinómico, es decir, la relación entre el tamaño del problema y su tiempo de ejecución es polinómica. Éstos son problemas agrupados en el conjunto P. Los problemas con coste factorial o combinatorio están agrupados en NP. Estos problemas no tienen una solución práctica, es decir, una máquina no puede resolverlos en un tiempo razonable.
| Tabla de contenidos |
Presentación
Un problema dado puede verse como un conjunto de preguntas relacionadas, donde cada pregunta se representa por una cadena de caracteres de tamaño finito. Por ejemplo, el problema FACTORIZAR se describe como: Dado un entero escrito en notación binaria, retornar todos los factores primos de ese número. Una pregunta sobre un entero específico se llama una instancia. por ejemplo, "Encontrar los factores primos del número 15" es una instancia del problema FACTORIZAR.
La complejidad en tiempo de un problema es el número de pasos que toma resolver una instancia de un problema, a partir del tamaño de la entrada utilizando el algoritmo más eficiente a disposición. Intuitivamente, si se toma una instancia con entrada de longitud n que puede resolverse en n² pasos, se dice que ese problema tiene una complejidad en tiempo de n². Por supuesto, el número exacto de pasos depende de la máquina en la que se implementa, del lenguaje utilizado y de otros factores. Para no tener que hablar del costo exacto de un cálculo se utiliza la notación O. Cuando un problema tiene costo en tiempo O(n²) en una configuración de computador y lenguaje dado este costo sera el mismo en la mayoría de los computadores, de manera que esta notación generaliza la noción de coste independientemente del equipo utilizado.
Ejemplos
- Extraer cualquier elemento de un vector. La indexación en un vector o array, lleva el mismo tiempo sea cual fuere el índice que se quiera buscar. Por tanto es una operación de complejidad constante O(1).
- Buscar en un diccionario tiene complejidad logarítmica. Se puede iniciar la búsqueda de una palabra por la mitad del diccionario. Inmediatamente se sabe si se ha encontrado la palabra o, en el caso contrario, en cuál de las dos mitades hay que repetir el proceso (es un proceso recursivo) hasta llegar al resultado. En cada (sub)búsqueda el problema (las páginas en las que la palabra puede estar) se ha reducido a la mitad, lo que se corresponde con la función logarítmica. Este procedimiento de búsqueda (conocido como búsqueda binaria) en una estructura ordenada tiene complejidad logarítmica O(ln n).
- El proceso más común para ordenar un conjunto de elementos tiene complejidad cuadrática. El procedimiento consiste en crear una colección vacía de elementos. A ella se añade, en orden, el menor elemento del conjunto original que aún no haya sido elegido, lo que implica hacer un recorrido completo del conjunto original (O(n), siendo n el número de elementos del conjunto). Este recorrido sobre el conjunto original se realiza hasta que queda todos sus elementos están en la secuencia de resultado. Se puede ver que hay que hacer n selecciones (se ordena todo el conjunto) cada una con un coste n de ejecución: el procedimiento es de orden cuadrático O(n²). Hay que aclarar que hay diversos algoritmos de ordenación con mejores resultados que el descrito.
Problemas de decisión
La mayor parte de los problemas en teoría de la complejidad tienen que ver con los problemas de decisión, que corresponden a poder dar una respuesta positiva o negativa a un problema dado. Por ejemplo, el problema ES-PRIMO se puede describir como: Dado un entero, responder si ese npumero es primo o no. Un problema de decisión es equivalente a un lenguaje formal, que es un conjunto de palabras de longitud finita en un lenguaje dado. Para un problema de decisión dado, el lenguaje equivalente es el conjunto de entradas para el cual la respuesta es positiva.
Los problemas de decisión son importantes porque casi todo problema puede ser transformado en un problema de decisión. Por ejemplo el problema CONTIENE-FACTORES descrito como: Dado un enteros n y k decidir si n tiene algún factor menor que k. Si se puede resolver CONTIENE-FACTORES con una cierta cantidad de recursos, su solución se puede utilizar para resolver FACTORIZAR con los mismos recursos, realizando una búsqueda binaria sobre k hasta encontrar el más pequeño factor de n, luedo se divide ese factor y se repite el proceso hasta encontrar todos los factores.
En teoría de la complejidad, generalmente se distingue entre soluciones positivas o negativas. Por ejemplo, el conjunto NP se define como el conjunto de los problemas en donde las respuestas positivas pueden ser verificadas muy rápidamente (es decir, en tiempo polinómico). El conjunto Co-P es el conjunto de problemas donde las respuestas negativas pueden ser verificadas rápidamente. El prefijo "Co" abrevia "complemento". El complemento de un problema es aquel en donde las respuestas positivas y negativas están intercambiadas, como entre ES-COMPUESTO y ES-PRIMO.
Un resultado importante en teoría de la complejidad es el hecho de que independientemente de la dificultad de un problema (es decir de cuantos recursos de espacio y tiempo necesita), siempre habrá problemas más difíciles. Esto lo determina en el caso de los costes en tiempo el teorema de la jerarquía temporal. De éste se deriva también un teorema similar con respecto el espacio.
Clases de complejidad
Los problemas de decisión se clasifican en conjuntos de complejidad comparable llamados clases de complejidad.
La clase de complejidad P es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina determinista en tiempo polinomial, lo que corresponde intuitivamente a problemas que pueden ser resueltos aún el el peor de sus casos.
La clase de complejidad NP es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina no-determinista en tiempo polinómico. Esta clase contiene muchos problemas que se desean resolver en la práctica, incluyendo el problema de satisfacibilidad booleana, el problema del camino Hamiltoneano y el problema de la cobertura de vértices. Todos los problemas de esta clase tiene la propiedad de que su solución puede ser verificada efectivamente.
La pregunta P=NP
El saber si las clases P y NP son iguales es el más importante problema abierto en Computación teórica. Inclusive hay un premio de un millón de dolares para quien lo resuelva.
Preguntas como esta motivan la introducción de los conceptos de hard (difícil) y completo. Un conjunto X de problemas es hard con respecto a un conjunto de problemas Y si todo problema en Y puede ser transformado sencillamente en algún problema de X con la misma respuesta. El término sencillo se define precisamente en cada caso. El más importante conjunto hard es NP-hard. En conjuntoX es completo para Y si es hard para Y y es también un subconjunto de Y. El conjunto completo más importante es NP-completo.
Investigadores en el área
- Stephen Cook
- Juris Hartmanis
- Richard Karp
- Leonid Levin
- Alexander Razborov
- Walter Savitch
- Richard Stearns
Véase también:
Enlaces externos
- The Complexity Zoo (en inglés)
| clases de complejidad más importantes |
| L | NL | P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C |
| PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH |