Complejidad Computacional

• ¿Qué es un problema?
  • Definición de un problema en formato estándar
  • Problemas de Optimización
  • Problemas de Decisión
• Análisis de Algoritmos
  • Algoritmo Eficiente
• Problemas indecidibles y no computables
  • TBD
  • ¿Quién es $M_D$?
  • Verificar donde va esto
    • Demostrar que $L_{BH}$ no es decidible:
  • TBD
  • Definición:
    • Busy Beaver
    • Demostrar que $BB(n)$ no es computable
  • TBD
• Problemas de Decisión
  • TBD
• TBD
• De Optimización a Decisión
• Verificación de TSP
  • Algoritmo CheckTSP

¿Qué es un problema?

Un problema es una cuestión que se plantea para encontrar un dato desconocido (salida) a partir de datos conocidos (entrada).

Definición de un problema en formato estándar

Se traducirá la palabra “instance” como ejemplar.

Ejemplar genérico: Conjunto de parámetros del problema y sus restricciones.

Enunciado objetivo: Descripción, en términos de los parámetros, de las características que ebe satisfacer la salida para ser considerada respuesta del problema.

Ejemplo:

1. Dada una secuencia $S$ de números, determinar el máximo de $S$. Ambigüedad

2. Listar todos los primos positivos. No es razonable

3. Encontrar el elemento mínimo de una secuencia finita y no vacia de números reales.

   Ejemplar genérico: Una secuencia $\{ x_0, x_1, x_2, \dots, x_{n-1} \}$ de $n$ números reales tal que $n \geq 1$

   Enunciado objetivo: Determinar el mínimo de $\{ x_0, x_1, x_2, \dots, x_{n-1} \}$, es decir, encontrar $x \in \{ x_0, x_1, x_2, \dots, x_{n-1} \}$ tal que $x \leq x_i$, para toda $0 \leq i \leq n-1$.

4. Dada una secuencia finita y no vacia de números naturales, encontrar el conjunto de los primeros 100 primos de $\mathbb{N}$ en el conjunto.

   Ejemplar genérico: Una secuencia $\{ u_0, n_1, \dots, n_{m-1} \}$ de $m$ números naturales tales que $m \geq 1$.

   TBD

Problemas de Optimización

• Tienen asociado un conjunto llamado conjunto de soluciones factibles
• Tienen asociada una función $f:\mathfrak{F} \rightarrow \mathbb{R}$ llamada función de peso o función de costo.
• El objetivo es encontar un elemento de $\mathfrak{F}$ que minimice o máximice $f$.

Ejemplo TSP

• Ejemplar Genérico: Un conjunto $C = \{ c_1, c_2, \dots, c_n \}$ de $n$ ciudades y una función distancia $d: C² \rightarrow R$ entre todo par de ciudades.
• Enunciado de Optimización: Determinar $t \in \mathfrak{F} \rightarrow \mathbb{R}$ tal que
  1. $\mathfrak{F} = \{ < c_{\theta_{1} }, c_{\theta_2}, \dots, c_{\theta_\N}> | \theta \text{ es una permutación de \{1,2,\dots, N \}} \}$
  2. $f(<c_{\theta_1}, c_{\theta_2}, \dots, c_{\theta_\N}>) = (\sum^{n-1}_{i=1} d(c_{\theta_i},c_{\theta_{i+1})}) + d(c_{\theta_n}, c_{\theta_1})$

Problemas de Decisión

• Únicamente tienen dos posiibles salidas: SI ó NO.

Ejemplo SAT

• Ejemplar Genérico: Un conjunto $U = \{ u_1, u_2, \dots, u_n \}$ de $n$ variables booleanas y un conjunto $C = \{ c_1, c_2, \dots, c_n \}$de $m$ cláusulas sobre $U$.
• Pregunta de Decisión: ¿Existe una asignación de verdad $\tau : U \rightarrow \{ 0, 1\}$ tal que $\tau (c_i) = 1$, para toda $1 \leq i \leq m$.

Análisis de Algoritmos

• Tiempo de Ejecución $T_A (E)$ donde $E$ es un ejemplar del problema.

  Trabajamos con familias de ejemplares que tuvieran el mismo tamaño.

• Tamaño de entrada (o tamaño de un ejemplar)

  El número de elementos significativos del ejemplar que serán procesados

• Función de Complejidad Temporal $T_A : \mathbb{N} \times \mathbb{Z}$ donde $T_A(n)$ es el tiempo de ejecución del algoritmo $A$ sobre el conjunto de ejemplares de tamaño $n$.

• Algoritmos Polinomiales

  • Son algortmos que viven en $O(n^k)$, con $k \in \mathbb{N}^+$

Algoritmo Eficiente

Definición: Un algoritmo es eficiente si y sólo si es $O(n^k)$ en tiempo

Problemas indecidibles y no computables

$\Gamma aleatorio$ ¿Esperamos poder resolver $\Gamma con un algoritmo?$

$L_{HALT}$

TBD

¿Quién es $M_D$?

Para todo $i$, $M_D$ no es $M_i$

Si $M_0$ y $M_i$ se ejeciutan con $w_i$

• Si $M_i$ se detiene, $M_D$ no se detiene
• Si $M_i$ no se detiene, $M_D$ no se detiene. $\contradiction$

$\therefore$ $L_{HALT}$ no se puede reconocer por una máquina de Turing

Verificar donde va esto

$N$ si empieza con una cienta en blanco:

1. Escribir $w$
2. Simular $M$ con $w$

$L_{BLANK-HALT} = \{M \in \{0,1\}^* | M \text{ se detiene al empezar su ejecución con una cinta en blanco}\}$

Demostrar que $L_{BH}$ no es decidible:

Pregunta:

¿Qué significa que una máquina de Turing sea total? Son aquellas que dada cualquier entrada, siempre terminan

Suponer que existe $M_{BH}$ total que $L(M_{BH}) = L_{BH}$ $M_{HALT}$

TBD

Podemos querer funciones más complejas, podemos usar una Máquina de Turing para esto al leer de su cinta al terminar su ejecución.

Definición:

$f: \Sigma^* \rightarrow$ es computable si y solo si exíste una máquina de Turing total $M$, tal que $M$ con la entrada $w$ deja a $f(w)$ escrita en su cinta al terminar la ejecución.

Hay más funciones que lenguajes. Sí hay lenguajes no computables, debe haber funciones no computables.

Busy Beaver

$BB(n)$ es la máxima cantidad de pasos que puede ejecutar una máquina de Turing $M$ tak que $M$ tiene $n$ estados, $M$ se detiene cuando empieza con una cinta en blanco y $\Gamma = \{0,1\}$

¿Es $BB(n)$ computable?

Demostrar que $BB(n)$ no es computable

Suponer que $BB(n)$ es computable. Entonces existe $M_{BB}$ total que computa $BB(n)$ con la entrada n.

$M_{BLANK-HALT}$ con entrada $w_i$

1. Construye la cadena n donde n es la cantidad de estados de $M_i$

TBD

Problemas de Decisión

Sea $\Pi$ un problema de optimización. El problema de decisión asociado a $\Pi$ es:

• Ejemplar Genérico: Mismo conjunto de parámetros que $\Pi$ y un real $K$ con restricciones según la función de costo de $\Pi$.
• Pregunta de Decisión: ¿Existe $s \in \mathfrak{F}$ tal que
  • $K \leq f(s)?$ Si $\Pi$ es de minimización
  • $f(s) \leq K?$ Si $\Pi$ es de maximización

Ejemplo 1. Problema de la Ruta más corta

Dada una gráfica simple y no dirigida de orden $n$ y pesos en sus aristas, y dos vértices distinguidos $s$ y $t$, determinar la ruta más corta entre $s$ y $t$.

• Forma Estándar:
  • Ejemplar Genérico: Una gráfica $G=(V,E)$ simple y no dirigida de orden $n$, con función de peso en sus aristas $p: E \rightarrow \mathbb{R}$, y dos vértices distinguidos $s$ y $t$.
  • Enunciado Objetivo: Determinar $c \in \mathfrak{F}$ que minimice $f$ ó que $f(c)$ sea mínimo, donde
    • $\mathfrak{F} = \{ C | C \text{es un camino de } s \text{ a } t \text{ en } G \}$
    • $f : \mathfrak{F} \rightarrow \mathbb{R} \text{ tal que } f(C) = \text{longitud}(C)$
• Problema de Decisión.
  • Ejemplar Genérico: Una gráfica $G=(V,E)$ simple y no dirigida de orden $n$, con función de peso en sus aristas $p: E \rightarrow \mathbb{R}$, dos vértices distinguidos $s$ y $t$, y un real $K \leq \sum_{e \in E} p(e)$.
  • Pregunta de Decisión: ¿Existe $c \in \mathfrak{F}$ tal que $K \leq f(c)$?

Ejemplo 2. Problema del Empaquetamiento

Dados $n$ objetos $o_1, o_2, \dots, o_n$, de tamaños $s(o_i)\in \mathbb{Z}^+$; un entero positivo C tal que $s(o_i) \leq c$; y un conjunto de n contenedores de capacidad c. Determinar el menor número de contenedores para colocar o almacenar todos los objetos.

• Forma Estándar:
  • Ejemplar Genérico: Un conjunto $O = o_1, o_2, \dots, o_n$, de $n$ objetos, con una función de tamaño $s: O \rightarrow \mathbb{Z}^+$ $s(o_i)\in \mathbb{Z}^+$; un entero positivo C tal que $s(o_i) \leq c$; y un conjunto de n contenedores de capacidad c. Determinar el menor número de contenedores para colocar o almacenar todos los objetos.

TBD

• Enunciado Objetivo: Determinar $c \in \mathfrak{F}$ que minimice $f$ ó que $f(c)$ sea mínimo, donde
  • $\mathfrak{F} = \{ C | C \text{es un camino de } s \text{ a } t \text{ en } G \}$
  • $f : \mathfrak{F} \rightarrow \mathbb{R} \text{ tal que } f(C) = \text{longitud}(C)$
• Problema de Decisión.
  • Ejemplar Genérico: Una gráfica $G=(V,E)$ simple y no dirigida de orden $n$, con función de peso en sus aristas $p: E \rightarrow \mathbb{R}$, dos vértices distinguidos $s$ y $t$, y un real $K \leq \sum_{e \in E} p(e)$.
  • Pregunta de Decisión: ¿Existe $c \in \mathfrak{F}$ tal que $K \leq f(c)$?

TBD

Un óraculo hace predicciones

De Optimización a Decisión

• Idea Intuitiva
  • Ejemplar Genérico: Conjunto de parámetros de la versión de optimización y un real K acotado según la función de costo asociada.
  • Pregunta de Decisión: ¿Existe $s \in \mathfrak{F}$ tal que
    • $K \leq f(s)$? Minimización
    • $f(s) \leq K$? Maximización
• Convención
  • Ejemplar Genérico: Conjunto de parámetros de la versión de optimización y un real K acotado según la función de costo asociada.
  • Pregunta de Decisión: ¿Existe $s \in \mathfrak{f}$ tal que
    • $f(s) \leq K$? Minimización
    • $K \leq f(s)$? Maximización

Verificación de TSP

Cuando no podemos solucionar directamente un álgoritmo de forma determinista podemos usar un enfoque distinto basado en proponer soluciones y verificar sí cumplen nuestro críterio.

Algoritmo CheckTSP

• Entrada: Un conjunto $C = \{ c_1, c_2, \dots, c_n \}$ de $n$ ciudades, una función $d : C^2 \rightarrow \mathbb{R}^+$ de distancia, y un real positivo $K \leq \displaystyle \sum_{e \in E} d(e)$.
• Salida: YES, sí existe un tour $t \in \mathfrak{F}$ tal que $f(t) \leq K$. NO, en otro caso.