Teoría de Complejidad Computacional

TEORÍA DE LA COMPLEJIDAD COMPUTACIONAL
La teoría de complejidad computacional es una rama de la teoría de ciencias

computacionales, cuyo principal objetivo es comparar y clasificar los problemas de
acuerdo a la cantidad de recursos computacionales necesarios para resolverlos;
estos recursos pueden ser temporales: tiempo empleado en su ejecución, o
espaciales: cantidad de memoria utilizada.
Clases de complejidad
Para la clasificación de problemas existen clases de complejidad, una clase de
complejidad consiste en un conjunto de problemas de decisión, estos se pueden
definir como el problema de decidir si una frase pertenece a un conjunto dado de
frases; en un problema de decisión las respuestas posibles son “si” o “no”. Entre
las clases de complejidad, podemos encontrar la P y la NP.
Máquinas de Turing
Para entender el tema de complejidad computacional, se debe entender antes las
máquinas de Turing.
Una máquina de Turing es un modelo de una máquina que consiste en una cinta,
divida en celdas, infinita hacia la derecha y finita hacia la izquierda, un cabezal de
lectura y escritura que se me mueve a la derecha o a la izquierda, una celda a la
vez, un registro de estados que almacena el estado de la máquina y una tabla de
instrucciones. La entrada y salida de la máquina de Turing se da en símbolos
binarios (0,1), y las celdas que no tienen símbolo 0 o 1, se llenan con un símbolo
especial llamado “blanco”.
El funcionamiento de una máquina de Turing es sencillo, el cabezal se ubica en
una posición inicial, con un estado inicial, lee el valor, lo borra y escribe uno
nuevo, dependiendo de la tabla de instrucciones, de la forma:
(Estado, valor)→(estado, valor, dirección)
DEFINICIÓN
M=(Q,∑,T,s,b,F,δ),
Donde:
Q es un conjunto finito de estados.
∑ es un conjunto finito de símbolos distinto del espacio en blanco, denominado
alfabeto de máquina o de entrada.
T es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta (∑ ⊆T)
s∈Q es el estado inicial.
b∈T es un símbolo denominado blanco, y es el único símbolo que se puede
repetir un número infinito de veces.
F⊆Q es el conjunto de estados finales de aceptación.
δ: QxT→ QxTx{L,R} es una función parcial denominada función de transición,
donde L es un movimiento a la izquierda y R es el movimiento a la derecha.
EJEMPLO
Definimos una máquina de Turing sobre el alfabeto {0,1}, donde 0 representa el
símbolo blanco. La máquina comenzará su proceso situada sobre un símbolo "1"
de una serie. La máquina de Turing copiará el número de símbolos "1" que
encuentre hasta el primer blanco detrás de dicho símbolo blanco. Es decir,
posiciona el cabezal sobre el 1 situado en el extremo izquierdo, doblará el número
de símbolos 1, con un 0 en medio. Así, si tenemos la entrada "111" devolverá
"1110111", con "1111" devolverá "111101111", y sucesivamente.
El conjunto de estados es {s1, s2, s3, s4, s5} y el estado inicial es s1. La tabla que
describe la función de transición es la siguiente:
Estado Símbolo leído Símbolo escrito Mov. Estado sig.

s1 1 0 R s2
s2 1 1 R s2
s2 0 0 R s3
s3 0 1 L s4
s3 1 1 R s3
s4 1 1 L s4
s4 0 0 L s5
s5 1 1 L s5
s5 0 1 R s1
El funcionamiento de una computación de esta máquina puede mostrarse con el

siguiente ejemplo (en negrita se resalta la posición de la cabeza lectora/escritora):
Paso Estado Cinta
1 s1 11
2 s2 01
3 s2 010
4 s3 0100
5 s4 0101
6 s5 0101
7 s5 0101
8 s1 1101
9 s2 1001
10 s3 1001
11 s3 10010
12 s4 10011
13 s4 10011
14 s5 10011
15 s1 11011
Parada
La máquina realiza su proceso por medio de un bucle, en el estado inicial s 1,

reemplaza el primer 1 con un 0, y pasa al estado s 2, con el que avanza hacia la
derecha, saltando los símbolos 1 hasta un 0 (que debe existir), cuando lo
encuentra pasa al estado s3, con este estado avanza saltando los 1 hasta
encontrar otro 0 (la primera vez no habrá ningún 1). Una vez en el extremo
derecho, añade un 1. Después comienza el proceso de retorno; con s 4 vuelve a la
izquierda saltando los 1, cuando encuentra un 0 (en el medio de la secuencia),
pasa a s5 que continúa a la izquierda saltando los 1 hasta el 0 que se escribió al
principio. Se reemplaza de nuevo este 0 por 1, y pasa al símbolo siguiente, si es
un 1, se pasa a otra iteración del bucle, pasando al estado s1 de nuevo. Si es un
símbolo 0, será el símbolo central, con lo que la máquina se detiene al haber
finalizado el cómputo.
Máquina de Turing determinista
Una máquina de Turing es determinista si para cada par (estado, valor) existe
máximo una posibilidad de ejecución.
Máquina de Turing no determinista
Una máquina de Turing es no determinista si existe al menos un par (estado,
valor) con más de una posibilidad de ejecución, es decir, para un mismo par puede
haber dos o más instrucciones para realizar. En este caso, la máquina siempre
elige la posibilidad más acertada para llegar a un estado final de aceptación.
Clase de complejidad P
Es el conjunto de problemas de decisión que una máquina de Turing determinista
puede resolver en tiempo polinómico, O(n k). La mayoría de problemas corrientes
(ordenación, búsqueda…) pertenecen a esta clase.
Clase de complejidad NP
Es el conjunto de problemas de decisión que una máquina de Turing no
determinista puede resolver en tiempo polinómico, O(n k).
EJEMPLO
Consideremos, por ejemplo, el Problema de la suma de subconjuntos, que es un
ejemplo de un problema fácil de verificar, pero cuya respuesta se cree (pero no ha
sido demostrado) es difícil de calcular/hallar. Dado un conjunto de números
enteros, ¿Existe un subconjunto no vacío de ellos donde la suma de sus
elementos es igual a 0? por ejemplo, ¿Existe un subconjunto del conjunto {−2, −3,
15, 14, 7, −10} tal que la suma de sus elementos sea 0? La respuesta es SI, si
bien puede llevar algún tiempo encontrar un subconjunto que satisface el
requerimiento, según cual sea el tamaño del conjunto y subconjunto. Por otra
parte, si alguien afirma que la respuesta es: «sí, porque la suma de {−2, −3, −10,
15} es igual a cero», entonces lo podemos comprobar en forma muy rápida y
mediante unas pocas cuentas. Verificar que la suma del subconjunto es cero es un
proceso mucho más rápido que encontrar el subconjunto. La información
necesaria para verificar un resultado positivo/afirmativo es llamada un certificado.
Por lo que podemos concluir que dado los certificados apropiados, es posible
verificar rápidamente las respuestas afirmativas de nuestro problema (en tiempo
polinomial) y es ésta la razón por la que el problema se encuentra en NP.

Teoría de Complejidad Computacional

Cargado por

Copyright:

Formatos disponibles

Teoría de Complejidad Computacional

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Teoría de Complejidad Computacional

Cargado por

Copyright:

Formatos disponibles

TEORÍA DE LA COMPLEJIDAD COMPUTACIONAL

La teoría de complejidad computacional es una rama de la teoría de ciencias

Estado Símbolo leído Símbolo escrito Mov. Estado sig.

El funcionamiento de una computación de esta máquina puede mostrarse con el

La máquina realiza su proceso por medio de un bucle, en el estado inicial s 1,

También podría gustarte