complejidad computacional

Complejidad Computacional

Objetivo: Medir la complejidad computacional de un problema.
Vale decir: Medir la cantidad de recursos computacionales
necesarios para solucionar un problema.
- Tiempo.
- Espacio.
- ...
Para hacer esto primero tenemos que introducir la noci´n de
o
problema.
1

Problemas de decisi´n
o

Alfabeto A: Conjunto finito de s´
ımbolos.
- Ejemplo: A = {0, 1}.Palabra w: Secuencia finita de s´
ımbolos de A.
- Ejemplo: w = 01101.
A∗ : Conjunto de todas las palabras construidas con s´
ımbolos de A.
Lenguaje L: Conjunto de palabras.
- Ejemplo: L = {0n 1n | n ∈ N}.
2

Problemas de decisi´n
o
Problema de decisi´n asociado a un lenguaje L: Dado w ∈ A∗ ,
o
decidir si w ∈ L.
Ejemplo: Podemos ver SAT como un problema de decisi´n.
o
Supongamos queP = {p, q}:
- A = {p, q, ¬, ∧, ∨, →, ↔, (, )}
Algunas palabras de A∗ representan f´rmulas de L(P ), mientras que
o
otras tales como ¬¬ y p¬q ∧ ∧ ∨ q no representan f´rmulas.
o
- SAT = {w ∈ A∗ | w representa una f´rmula de L(P ) y w es
o
satisfacible}.
Ejercicio: Represente el problema de 3-coloraci´n de grafos como un
o
problema de decisi´n.
o
3

Complejidad de un problema dedecisi´n
o
La complejidad de un lenguaje L es la complejidad del problema de
decisi´n asociado a L.
o
¿Cu´ndo decimos que L puede ser solucionado eficientemente?
a
- Cuando existe un algoritmo eficiente que decide L.
Ejercicio: Muestre que L = {w ∈ {0, 1}∗ | n´mero de 0s y 1s en w es el
u
mismo} puede ser resuelto eficientemente.

¿Cu´ndo decimos que L es un problema dif´
a
ıcil?
- Cuandono existe un algoritmo eficiente que decide L.
4

M´quinas de Turing
a
¿C´mo podemos demostrar que un problema es dif´
o
ıcil?
- Para hacer esto, primero tenemos que formalizar la noci´n de
o
algoritmo.
¿Qu´ es un algoritmo? ¿Podemos formalizar este concepto?
e
- M´quinas de Turing: Intento por formalizar este concepto.
a
¿Podemos demostrar que las m´quinas de Turing capturan la
anoci´n de algoritmo?
o
- No, el concepto de algoritmo es intuitivo.
5

M´quinas de Turing
a
¿Por qu´ creemos que las m´quinas de Turing son una buena
e
a
formalizaci´n del concepto de algoritmo?
o
- Porque cada programa de una m´quina de Turing puede ser
a
implementado.
- Porque todos los algoritmos conocidos han podido ser
implementados en m´quinas de Turing.
a
- Porque todoslos otros intentos por formalizar este concepto
fueron reducidos a las m´quinas de Turing.
a
- Los mejores intentos resultaron ser equivalentes a las m´quinas
a
de Turing.
- Todos los intentos “razonables” fueron reducidos eficientemente.

- Tesis de Church: Algoritmo = M´quina de Turing.
a
6

M´quinas de Turing: Componentes
a

Dado: Alfabeto A que no contiene s´
ımbolo especial B.Componentes:
- Memoria: Arreglo infinito (en ambas direcciones) que en cada
posici´n almacena un s´
o
ımbolo de A ∪ {B}.
- Control: Conjunto finitos de estados, una cabeza lectora, un
estado inicial y un conjunto de estados finales.
- Programa: Conjunto de instrucciones.

7

M´quinas de Turing: Funcionamiento
a

Inicialmente:
- La m´quina recibe como entrada una palabra w.
a
-Coloca esta palabra en alguna parte del arreglo. En las posiciones
restantes el arreglo contiene s´
ımbolo blanco B.
- La cabeza lectora se coloca en la primera posici´n de w y la
o
m´quina queda en el estado inicial q0 .
a

8

M´quinas de Turing: Funcionamiento
a

En cada paso:
- La m´quina lee el s´
a
ımbolo a en la celda apuntada por la cabeza
lectora y determina en que estado qse encuentra.
- Busca en el programa una instrucci´n para (q, a). Si esta instrucci´n
o
o
no existe, entonces la m´quina se detiene.
a
- Si la instrucci´n existe, entonces la ejecuta: Escribe un s´
o
ımbolo en
la posici´n apuntada por la cabeza lectora, pasa a un nuevo estado
o
y mueve la cabeza lectora a la derecha o a la izquierda.

Si la m´quina se detiene en un estado final,...