Computabilidad

COMPUTABILIDAD
La Teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con una máquina deTuring. La teoría de la computabilidad se interesa a cuatro preguntas:
* ¿Qué problemas puede resolver una máquina de Turing?
* ¿Qué otros formalismos equivalen a las máquinas de Turing?
*¿Qué problemas requieren máquinas más poderosas?
* ¿Qué problemas requieren máquinas menos poderosas?
La teoría de la complejidad computacional clasifica las funciones computables según el uso quehacen de diversos recursos en diversos tipos de máquina.

Complejidad computacional
La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica,la complejidad inherente a la resolución de un problema computable. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmopara resolver un problema) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema). Se pueden estudiar igualmente otros parámetros, tales como el número deprocesadores necesarios para resolver el problema en paralelo. La teoría de la complejidad difiere de la teoría de la computabilidad en que ésta se ocupa de la factibilidad de expresar problemas comoalgoritmos 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 quese relaciona linealmente con su tamaño.
Hoy en día las computadoras resuelven problemas mediante algoritmos que tienen como máximo una complejidad o coste computacional polinómico, es decir, larelación entre el tamaño del problema y su tiempo de ejecución es polinómica. Éstos son problemas agrupados en la clase P. Los problemas que no pueden ser resueltos por nuestras computadoras (las...