Página de Guillaume Hoffmann

View on GitHub

% Clase 3: Tiempo de ejecución de MT. Clase P.

Complejidad Computacional

Medir lenguajes

  • queremos medir la dificultad de decidir lenguajes
  • en lugar de usar una regla o un termómetro para medir eso vamos a usar… ¡máquinas de Turing!
  • con cualquier medición, vienen las comparaciones: ¿hay lenguajes más “difíciles” que otros?
  • los lenguajes finitos son decidibles. Desde ahora consideremos los infinitos.

Medir el tiempo de ejecución

  • Medimos la relación entre el tamaño de una palabra y los recursos usados para decidir si pertenece a un lenguaje dado.
  • Una MT decide $L$ en tiempo $T(n)$ si su ejecución en cada entrada $x$ de tamaño $n$ necesita cómo máximo $T(n)$ pasos para decidir si $x$ pertenece a $L$ o no.
  • Acá $T(n)$ es una cota superior.

Teorema de incremento lineal de velocidad

Si $L$ es decidible por una máquina $M$ en tiempo $T(n)$, entonces para cualquiera constante $c \geq 1$, $L$ es decidible por una máquina $M’$ en tiempo $T(n)/c$.

Idea: Aumentar tamaño del alfabeto y conjunto de estados, y representar la información de manera más compacta.

¿Una definición floja?

Notacion O grande

  • Dadas funciones $f,g : \mathbb{N} \mapsto \mathbb{N}$, escribimos $f \in O(g)$ si existen $c > \mathbb{R}^+$ y $n \in \mathbb{N}$ tales que para todo $m > n$, $f(n) \geq c.g(n)$.
  • Decimos que $f$ es acotada por $g$ (módulo un factor multiplicativo) a partir de un cierto rango.
  • Informalmente, f no crece más rápido que g (multiplicada por una constante). Puede crecer más despacio o al mismo ritmo, no más rápido.
  • Ejemplo: $f(n)= 6n^3 + 2n^2 + 20n + 45$ , $f(n) \in O(n^3)$.

Ejemplo de algoritmo en tiempo O(1)

En O(1) están los algoritmos que se ejecutan siempre en la misma cantidad de pasos, sin importar el tamaño de la entrada:

bool IsFirstElementNull(IList<string> elements)
{
    return elements[0] == null;
}

O(n)

En O(n) están los algoritmos cuyo tiempo de ejecución crece de forma lineal y en proporción directa al tamaño de su entrada:

bool ContainsValue(IList<string> elements, string value)
{
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
}

$O(n^2)$

Algoritmos cuyo tiempo de ejecución crece de forma proporcional al cuadrado del tamaño de su entrada:

bool tieneDuplicados(IList<string> elements)
{
  for (var i = 0; i < elements.Count; i++)
  {
    for (var j = 0; j < elements.Count; j++)
    {
      if (i != j && elements[i] == elements[j])
        return true;
    }
  }
  return false;
}

$O(2^n)$

Algoritmos cuyo tiempo de ejecución se duplica cada vez que el tamaño de la entrada se incrementa de una unidad:

int Fibonacci(int number)
{
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

Clases de complejidad

Definición

Una clase de complejidad es un conjunto de lenguajes, definido por alguna noción de dificultad, a menudo a través de máquinas de Turing.

TIME(T(n))

Sea $T: \mathbb{N} \mapsto \mathbb{N}$.

Un lenguaje $L$ pertenece a la clase TIME(T(n)) si existe una máquina que corre en tiempo $cT(n)$ (para alguna constante $c > 0$) y decide $L$.

P

P = $\bigcup_{c \geq 1}$ TIME$(n^c)$

Es la clase de todos los lenguajes decidibles en tiempo polinomial.

Desafiando la definición de P

Sustituciones de MT: alfabeto

  • Si $L$ es decidible por una MT con un alfabeto $\Gamma$ en tiempo $T(n)$, entonces es decidible por una MT con alfabeto ${0,1,\square,\triangleright}$ en tiempo $(2 log_2(|\Gamma|) + 1)(T(n))$
  • Conclusión: un lenguaje que está en P, lo sigue siendo independientemente del alfabeto de la MT que usamos para afirmar que está en P.

Sustituciones de MT: cantidad de cintas

  • Si $L$ es decidible por una MT con $k \geq 2$ cintas en tiempo $T(n)$, entonces es decidible por una MT con 1 cinta en tiempo $O(T(n)^2)$
  • Conclusión: un lenguaje que está en P, lo sigue siendo independientemente de la cantidad de cintas de la MT que usamos para afirmar que está en P.

Más resultados similares

Más resultados de cambio de tipo de MT (con costo polinomial en tiempo):

  • tener cintas infinitas en las dos direcciones o en una sola dirección
  • tener cintas de $k$ dimensiones a cintas de $1$ dimensión
  • que los movimientos posibles de cabezales incluyan detenerse, o no
  • tener acceso secuencial o aleatorio a la memoria, etc.

Con P, no importa tanto el modelo de cálculo

  • Cuando vamos a describir algoritmos para P, no es necesario describir máquinas de Turing.
  • Las operaciones aritméticas (eg $+$, $-$, $.$, $/$) con input codificados en binario se pueden hacer en tiempo polinomial
  • Un algoritmo en pseudocódigo con complejidad polinomial basta para afirmar que un lenguaje está en P (porque es compilable a una MT polinomial)

Codificación

Hemos visto que la definición precisa del tipo de MT o del lenguaje de programación no importa (si trabajamos con P).

Pero ¿importarám las distintas codificaciones de un mismo problema?

Grafos y valores numéricos

  • ¿Importa si codificamos un grafo como matriz de adyacencia o como lista?
  • No porque convertir una representación en otra se puede hacer en tiempo polinomial.
  • ¿Importa si codificamos los enteros en base 1, 2, 10?
  • Sí, hay una diferencia entre base 1 y las otras, puede haber una diferencia exponencial.
  • Conclusion: evitar la base 1, el resto vale.
  • Por ej: un grafo de con $n$ nodos es un input de tamaño $n$ y listo.

Ejemplos y ejercicios

Ejemplo de lenguaje en P: PATH

Ejemplo de lenguaje en P: RELPRIME

Ejercicios

Mostrar que los lenguajes siguientes están en P:

  1. CONNECTED: el lenguaje de los grafos conectados. Es decir, G pertenece a CONNECTED si para cualquier par de nodos u,v de G es conectado por un camino
  2. TRIANGLEFREE: el lenguaje de los grafos que no contienen ningun triángulo de nodos (es decir, tres nodos $u$, $v$, $w$ de nodos distintos conectados).

Apunte

Apuntes