Complejidad computacional

Universidad Autónoma de Nuevo León

Facultad de Ingeniaría Mecánica y Eléctrica

Teoría Matemática de la Computación
Complejidad Computacional

Nombre: Andrés Mendiola Mendoza
Matricula: 1240796 Hora: M4
Salón: 3105

San Nicolás de los Garza, Nuevo León20 De Octubre del 2007
COMPLEJIDAD COMPUTACIONAL.

COMPLEJIDADA ESPACIAL.

La complejidad de una computación se mide por la cantidad de espacio y tiempo que consume. Las computaciones eficientes tienen una exigencia de recursos relativamente pequeña. Los recursos que necesita una computación que acepta cadenas de algún lenguaje, puede depender del tamaño olongitud de la cadena de entrada.

Si una maquina de Turing con k cintas de trabajo y cuya cota espacial es S(n) acepta el lenguaje L, entonces una maquina de Turing con una cinta de trabajo y una cota espacial S(n) también lo acepta.

Lo antes mencionado dice que el número de cintas usadas al aceptar un lenguaje, no afecta la complejidad espacial de L. Además de poder comprimirse por medio de unfactor constante la capacidad de espacio de una cinta que se usa al aceptar un lenguaje, codificando distintos símbolos de la cinta en uno.

Sea L un lenguaje aceptado por una maquina de Turing M con k cintas de trabajo, cuya cota espacial es S(n). para todo c>0, hay una maquina de Turing espacialmente acotada por cS(n) que acepta L.

Como resultado de lo antes mencionado se puede comparar elcomportamiento asintótico de las cotas espaciales cuando comparemos requerimientos espaciales de la maquina de Turing. Por tanto, la maquina de Turing M1 con cota espacial S1(n) = n2 + 2n +1 y la maquina de Turing M2 con cota espacial S2 = 3n2 – 1, tienen las dos complejidad espacial idéntica S(n) = n2 . Por otro lado la complejidad espacial de n3 es menor que las complejidades espaciales n4 o 2n.Recuerde que una DI de un maquina de Turing tiene en cuenta tanto el estado actual como el contenido actual de la cinta. De esta forma una cota espacial para una maquina de Turing proporciona una cota sobre el tamaño de una DI.

Si se unieran la información que aporta una cota espacial con lo que se sabe acerca del tamaño de conjuntos de estados y símbolos de cinta, se tiene como resultadouna cota cota para el numero de movimientos que se realizan en una secuencia de aceptación.

Sea M una maquina de Turing de k cintas con complejidad espacial S(n), donde S(n)> logn. Entonces existe una constante c para la cual, si w es una entrada cualquiera con lwl = n con lo cual:

a) M tiene como máximo cS(n) descripciones instantáneas.
b) Si M acepta w, entonces lo hace en cS(n)movimientos como máximo.

Se dice que una función S(n) es totalmente es totalmente construible en espacio si hay una maquina de Turing MS que tiene una cota espacial S(n) y, para toda entrada de longitud n, MS usa exactamente la S(n) celdas de cinta de trabajo.

Teorema de Savitch.- Si S(n) es totalmente construible en espacio y M es una maquina con Turing no determinista de complejidadespacial S(n), entonces hay una maquina de Turing no determinista, con complejidad espacial (S(n))2 para la cual L(M) = L(M’).

COMPLEJIDAD TEMPORAL.

A pesar de que el espacio es un recurso importante de cualquier maquina de Turing, el tiempo de computación también es importante. La complejidad temporal de las computaciones de maquinas de Turing, depende del tamaño de la cadena de entrada.

Eltiempo se mide por medio del numero de movimientos que hace una maquina Turing.

Sea M una maquina de turing de k cintas. Suponemos que M realiza como máximo T:N N
Entonces se dice que M tiene complejidad temporal T(n) o que es una maquina de Turing con cota temporal T(n). Además se dice que L(M) es un lenguaje temporalmente acotado por T(n) o con complejidad temporal T(n).

Sea k > 1....