Lagrimas de angel

Los lenguajes formales que son aceptados por una máquina de Turing son exactamente aquellos que pueden ser generados por una gramática formal. El cálculo Lambda es una forma de definir funciones. Las funciones que pueden se computadas con el cálculo Lambda son exactamente aquellas que pueden ser computadas con una máquina de Turing. Estos tres formalismos, las máquinas de Turing, los lenguajesformales y el cálculo Lambda son formalismos muy disímiles y fueron desarrollados por diferentes personas. Sin embargo, ellos son todos equivalentes y tienen el mismo poder de expresión. Generalmente se toma esta notable coincidencia como evidencia de que la tesis de Church-Turing es cierta, que la afirmación de que la noción intuitiva de algoritmo o procedimiento efectivo de cómputo corresponde ala noción de cómputo en una máquina de Turing.

Problema p
En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor que un cierto valor calculado a partir del número de variables implicadas (generalmente variables de entrada) usando una fórmula polinómica, se dice que dicho problema se puede resolver en un tiempo polinómico.Por ejemplo, si determinar el camino óptimo que debe recorrer un cartero que pasa por N casas necesita menos de 50N2+N segundos, entonces el problema es resoluble en un "tiempo polinómico".
De esa manera, tiempos de 2n2+5n, o 4n6+7n4-2n2 son polinómicos; pero 2n no lo es.
Dentro de los tiempos polinómicos, podemos distinguir los logarítmicos (log(n)), los lineales (n), los cuadráticos (n2),cúbicos (n3), etc.
Clases de complejidad
En teoría de la complejidad, la clase de complejidad de los problemas de decisión que pueden ser resueltos en tiempo polinómico calculado a partir de la entrada por una máquina de Turing determinista es llamada P. Cuando se trata de una máquina de Turing no-determinista, la clase se llama NP. Una de las preguntas abiertas más importantes en la actualidad esdescubrir si estas clases son diferentes o no. El Clay Mathematics Institute ofrece un millón de dólares a quien sea capaz de responder a esa pregunta.
[pic]
[pic]
Diagrama de clases de complejidad. Si P = NP, P contendría las zonas NP y NP-completo.
Los problemas NP-completos pueden ser descritos como los problemas en NP que tienen menos posibilidades de estar en P (Ver NP-completo para unadefinición precisa). Actualmente los investigadores piensan que las clases cumplen con el diagrama mostrado por lo que P y NP-completo tendrían intersección vacía.
La importancia de la pregunta P = NP radica en que de encontrarse un algoritmo en P para un problema NP-completo, todos los problemas NP-completos (y por ende, todos los problemas de NP) tendrían soluciones en tiempo polinómico.

Clasesde Complejidad
● 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.
● Los problemas se clasifican en conjuntos o
clases de complejidad (L, NL, P, PCompleto,
NP, NP-Completo, NP Duro...)
● Nosotros nos vamos a centrar en las clases
P y NP yfundamentalmente en esta última.

Problemas P y NP
● LA CLASE P contiene aquellos problemas de decisión
que pueden ser resueltos en tiempo polinómico por una
MT determinista, esto es, aquellas en las que para
cada par estado y símbolo exista a lo sumo una
posibilidad de ejecución. Los problemas de
complejidad polinómica son tratables, es decir, en la
práctica se pueden resolver en un tiemporazonable.
● LA CLASE NP contiene los problemas de decisión que
son resueltos por una MT no determinista en tiempo
polinómico y de ahí su nombre: Non-Deterministic
Polynomial-time.

Problemas P y NP ii
● Naturalmente, cualquier problema en P
también se encuentra en NP:
✔ Si una máquina de Turing determinista resuelve el
problema, una no determinista también y en igual tiempo
(MTD es un caso...