Problemas en P, NP y NP Completos

Dentro de la teoría matemática de la computación, se estudia la complejidad en función del tiempo y el espacio (almacenamiento), además existen problemas computacionalmente resolubles e irresolubles (es cierto, las computadoras no pueden resolver todos los problemas). dentro de los resolubles me centrare en los que tienen coste en tiempo. Existe la teoría de que se pueden agrupar en conjuntos, además de tratar de de demostrar sus limites he intersecciones y uniones. Veamos:

P: es el conjunto de problemas que una Maquina Turing Determinista (en adelante MT )puede resolver en un tiempo O(p(n)) es decir en tiempo polinómico.

NP: es el conjunto de problemas que pueden ser resueltos por una maquina de Turing No determinista (En adelante nMT) en tiempo polinomial O(p(n)).

NP-C: es el subconjunto NP de problemas de decisión (Si o No) tales que todo problema en NP se pueda reducir a NP-C. estos son considerados los problemas mas difíciles (En coste de tiempo). ejemplo el problema de satisfacibilidad Booleana (SAT), tiene un O(2^n) y se comprueba que es NP-C.

EXPTIME: Estos problemas tienen solución, sin embargo, son intratables por el alto costo en tiempo, pues su tiempo se define como O(2^P(n)) donde P(n) es un polinomio. Ejemplo de problemas en EXPTIME esta el de las jugadas posibles en el ajedrez. al parecer son 10^123 (Nótese que el problema no es saber cuantas, sino describir cada una de ellas).

Suponiendo la complejidad de SAT, si se duplicara la potencia de calculo de las maquinas actuales, entonces resolveríamos el mismo problema en 2^(n-1), si se cuadruplicara 2^(n-2), aunque la ley de Moore predice este crecimiento y en lo particular creo que la potencia de calculo máxima que puede alcanzar una computadora esta limitada a las leyes de la física (después de todo no podemos hacer que la luz viaje mas rápido ¿o si?), sin embargo cuando n es un numero muy grande (n→∞) tardaríamos mucho tiempo en alcanzar su resultado (este fenómeno es peor en EXPTIME), actualmente se tratan los problemas en NP-C con aproximaciones, probabilidad, técnicas heurísticas y algoritmos genéticos, sin embargo no se ha conseguido un mejor tiempo que el exponencial.

La próxima entrada hablara de MT, nMT y computadoras cuánticas.