Trabajo de tesis

¿D´nde estamos? o
El objetivo de esta secci´n es introducir la noci´n de complejidad o o computacional. - Cuanto cuesta resolver un problema. Hasta ahora: - Formalizamos la noci´n de algoritmo a trav´s de las M´quinas de o e a Turing. - Demostramos que hay problemas muy dif´ ıciles: indecidibles. Lo que viene: - Definir la complejidad de un algoritmo. - Estudiar la complejidad de un problema.Antes de esto: M´quinas de Turing no deterministas. a
38

M´quinas de Turing no deterministas a
Notaci´n: A las m´quinas de Turing que hemos visto hasta ahora las o a llamamos deterministas.

M´quina de Turing no determinista: (Q, A, q0 , δ, F ) a - Q es un conjunto finito de estados. - A es un alfabeto. - q0 es el estado inicial (q0 ∈ Q). - F es un conjunto de estados finales (F = ∅). - δ ⊆ Q ×A × Q × A × {I, D}: Relaci´n de transici´n. o o Asumimos que δ = ∅.
39

M´quinas de Turing no deterministas: Funcionamiento a
Inicialmente: Tal como en una MT determinista. 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 q se encuentra. - Determina el conjunto de todas las instrucciones para (q, a). Si este conjunto esvac´ entonces la m´quina se detiene. ıo, a - Si el conjunto no es vac´ entonces escoge una instrucci´n de este ıo, o conjunto y la ejecuta.

Si la m´quina se detiene en un estado final, entonces la m´quina a a acepta w.
40

M´quinas de Turing no deterministas: Lenguaje aceptado a

Dada una m´quina de Turing M no determinista con alfabeto A: a L(M ) = {w ∈ A∗ | existe alguna ejecuci´n de M o conentrada w que termina en un estado final}.

Ejercicio: Sea L = {w ∈ {0}∗ | el largo de w es divisible por 2 ´ 3}. o Construya una MT no determinista que acepte L y que s´lo mueva su o cabeza a la derecha.

Ejercicio: ¿Puede hacer lo mismo con una MT determinista?

41

M´quinas de Turing no deterministas: Poder de computaci´n a o

¿Son las m´quinas de Turing no deterministas m´spoderosas que a a las deterministas? Teorema: Para cada MT no determinista M , existe una MT determinista M tal que M y M se detienen en las mismas palabras y L(M ) = L(M ). Ejercicio: Demuestre el teorema.

42

Complejidad de un algoritmo
Dado: MT determinista M con alfabeto A que para en todas las entradas.
- Paso de M : ejecutar una instrucci´n de la funci´n de transici´n. o o o - tiempo M (w):n´mero de pasos ejecutados por M con entrada w. u

Dado un n´mero natural n: u tM (n) = m´x{ tiempo M (w) | w ∈ A∗ y |w| = n}. a

tM : tiempo de ejecuci´n de M en el peor caso. o
43

Complejidad de un problema

Un lenguaje L puede ser aceptado en tiempo t si es que existe una MT determinista M tal que: - M para en todas las entradas. - L = L(M ). - tM es O(t), vale decir, existe c ∈ R+ yn0 ∈ N tal que tM (n) ≤ c · t(n) para todo n ≥ n0 . El tiempo para computar una funci´n f se define de la misma o forma.

44

Clases de complejidad
Dado: alfabeto A. DTIME(t): conjunto de todos los lenguajes L ⊆ A∗ que pueden ser aceptados en tiempo t. Dos clases fundamentales: PTIME EXPTIME =
k∈N

DTIME(nk ). DTIME(2 ).
k∈N nk

=

PTIME: conjunto de todos los problemas que puedenser solucionados eficientemente.
45

Un problema fundamental
El problema fundamental de nuestra disciplina: Dado un problema, encontrar un algoritmo eficiente para solucionarlo o demostrar que no existe tal algoritmo. Primera parte (puede ser dif´ ıcil): Demostrar que L ∈ DTIME(t).
- Si L = {w ∈ {0}∗ | largo de w es par}, entonces L ∈ DTIME(n).

Segunda parte (es dif´ ıcil): Demostrar que L ∈DTIME(t).
- ¿Es cierto que SAT ∈ PTIME?

¿Como podemos atacar el segundo problema?
46

La noci´n de completitud: Reducci´n polinomial o o
Dado: Lenguajes L1 y L2 con alfabeto A. Definici´n: L1 es reducible en tiempo polinomial a L2 si existe o una funci´n f computable en tiempo polinomial tal que para todo o w ∈ A∗ : w ∈ L1 si y s´lo si f (w) ∈ L2 . o

Corolario: Asuma que L1 es...