Complejidad computacional

La complejidad computacional es el campo de la teoría de la computación que estudia teóricamente la complejidad inseparable a la resolución de un problema. Los recursos que normalmente se estudian son:

• El tiempo: que por medio de una aproximación al número y patrón de pasos de ejecución de un algoritmo para solucionar algún problema.
• El espacio: que por medio de una aproximación a la cantidad de memoria que utilizamos para solucionar algún problema. 

Podemos estudiar al igual otros parámetros, así como el número de procesadores que necesitamos para solucionar el problema en equivalente. La teoría de la complejidad se distingue de la teoría de la computabilidad en que ésta se necesita de la posibilidad de manifestar problemas como algoritmos más efectivos sin tomar en cuenta los recursos necesarios para esto.

Los problemas que tienen una solución con orden de complejidad lineal son los problemas que se resuelven en un tiempo que se vincula linealmente con su tamaño.

Los problemas de decisión son clasificados en conjuntos de complejidad comparable llamados clases de complejidad.

Clases de complejidad

Una clase de complejidad es un conjunto de problemas de decisión de complejidad relacionada. Es el conjunto de problemas de decisión que se pueden resolver por una máquina turing utilizando O(f(n)) del recurso R, donde el tamaño n es la entrada.

Clase de complejidad P

Cuando el tiempo de ejecución de un algoritmo, es por cual se obtiene una solución al problema, es menor que el cierto valor calculado partiendo del número de variables incluidas, normalmente son variables de entrada, utilizando una fórmula polinómica, se puede decir que el problema lo podemos resolver en un tiempo polinómico.

La clase de complejidad de los problemas de decisión que se pueden resolver en tiempo polinómico al calcular partiendo de la entrada gracias a máquina de Turing determinista es llamada P.

Ejemplo de tiempo polinomial para generar números primos de forma aleatoria.

Algoritmo Obtención de un número primo aleatorio

/*Basado en el postulado de Bertrand*/

Entrada: Un número natural n.

Salida : P (el número primo aleatorio buscado).

1.-  P <--  Función Genera_numero_aleatorio_en_intervalo [n, 2n]

2.-  Mientras P no sea un número primo haga lo siguiente:

   1.-  P <-- P + 1

   2.-  Si (P = 2n) entonces:

      1.-  P <-- n

3.-  Retorne P

Clase de complejidad NP

¿Qué es NP?, NP son las siglas en inglés de nondeterministic polynomial time ("tiempo polinomial no determinista"). Es el conjunto de problemas que se pueden resolver en tiempo polinómico por una máquina de Turing no determinista.

La importancia de esta clase de problemas de decisión es que tiene muchos problemas de búsqueda y de optimización, los cuales se desea saber si existe una especifica solución o si existe una mejor solución que las que ya conocemos.

Por la importancia que tiene, con muchos esfuerzos han tratado de encontrar algoritmos que decidan algún problema de NP en tiempo polinómico. Aunque, parezca que para algunos problemas de NP (los del conjunto NP-completo) no se puede encontrar un algoritmo mejor que solamente realizar una búsqueda profunda.

Ejemplo de NP, el problema del viajante

El problema del viajante es un ejemplo que muestra y analiza la problemática que esta debajo de algunos tipos de problemas matemáticos que antes parecen tener una solución relativamente fácil, y en la práctica presentan un gran problema.

Se conoce la respuesta al problema o bueno, la forma de resolverlo, pero sólo en teoría, en la práctica la solución no se aplica debido al tiempo que computacionalmente se necesita para conseguir su resultado.

El también conocido como problema del viajante de comercio o por sus siglas en inglés TSP: Travelling Salesman Problem, es de los problemas más famosos y tal vez el mejor estudiado en el campo de la optimización combinatoria computacional. A pesar de la aparente sencillez de su planteamiento, es uno de los más complejos de resolver y existen demostraciones que visten la complejidad de su solución a la de otros problemas aparentemente mucho más complejos que han retado a los matemáticos.

Imagen que representa este problema, ¿cual es la ruta más optima que se debe tomar para visitar todas las ciudades?

Ejemplo de recorrido del problema del viajante (vídeo que encontré).

Esquema del problema del viajante para m rutas (m-TSP) que consiste en obtener el recorrido mínimo para ''m'' vehículos que tienen que pasar por n puntos a partir de un punto origen.

NP-Completo

Un NP-completo es el sub-conjunto de los problemas de decisión en NP por esto todo problema en NP se puede transformar en cada uno de los problemas de NP-completo. Podemos decir que los problemas de NP-completo son los problemas con mayor dificultad de NP y es muy probable que no puedan formar parte de la clase de complejidad P.

Un problema de decisión C es NP-completo si se cumple lo siguiente:

• C es un problema NP.
• Todo problema de NP se puede transformar polinómicamente en C.

Podemos demostrar que C es NP comprobando que un aspirante a solución de C puede ser examinado en tiempo polinómico.

Una transformación polinómica de L en C es un algoritmo confirmando que transforma instancias de l ∈ L en instancias de c ∈ C, por esto la respuesta a c es positiva si y sólo si la respuesta a l lo es.
Como resultado de esta descripción, si tenemos un algoritmo en P para C, tendríamos una solución en P para todos los problemas de NP.

Ejemplo de NP-completo, problema de la clique

Una clique en un grafo, un conjunto de vértices dos a dos adyacentes. 

Los vértices 1, 2 y 5 forman una clique porque cada uno tiene un arco que le une a los otros. En cambio, los vértices 2, 3 y 4 no, dado que 2 y 4 no son adyacentes.

El problema de la clique es un problema de optimización para definir cuándo un grafo tiene una clique de por lo menos tamaño k. Cuando tengamos k o más vertices que forman una clique, es trivial verificar que lo son, por esto es un problema NP. El problema que corresponde de optimización, consiste en hallar una clique de tamaño máximo en un grafo. Este problema se puede expresar como un problema de decisión si la pregunta que se hace es saber si existe una clique de tamaño k en el grafo.

Algoritmo para resolver este problema

Algoritmo de fuerza bruta

La búsqueda por fuerza bruta, búsqueda combinatoria, búsqueda exhaustiva o simplemente fuerza bruta, es una técnica trivial de las más usadas, consiste en enumerar ordenadamente todos los posibles aspirantes para la solución de un problema, su fin es el de reconocer si dicho aspirante satisface la solución al mismo.

Un ejemplo de esto, es cuando registramos todos los sub-conjuntos de vértices y comprobamos cada uno si forman una clique. 

Funcionamiento del algoritmo de fuerza bruta, cuando realiza la búsqueda combinatoria. 

Referencias:

Complejidad computacional
Complejidad P
Complejidad NP
NP-completo