Reducciones Parametrizadas e Intratabilidad

Antes que nada debo aclarar un punto, la entrada del 24 de Febrero en realidad tendría que venir despues de la que primera que esta en marzo, por ahi hubo un error tecnico de mi parte, por lo cual me referire a la sesion anterior como la de "Complejidad Parametrizada", una vez hecha la aclaracion empezaré:

En la sesion anterior se introdujo lo que es parametrización, problemas parametrizados y la tratabilidad parametrizada y vimos la clase FPT, ahora abordaremos un tema que es muy importante (además de la complejidad descriptiva) debido a que nos ayudara a definir otras clases de complejidad parametrizada, las reducciones tratables de parametro fijo (Fixed parameter tractable reductions)

Reducciones tratables de parametro fijo.
Principalmente en este apartado se introducen definiciones útiles para temas que abordaremos más adelante.

Sea (Q, κ) y (Q', κ') problemas parametrizados sobre un alfabeto Σ y Σ' respectivamente. Una reduccion fpt de (Q, κ) a (Q', κ') es un mapeo R: Σ &rarrow; Σ' tal que:

1) Para toda x ∈ Σ tenemos que (x ∈ Q ⇔ R(x) ∈ Q')
2) R es computable por un algoritmo-fpt (con respecto a κ). Esto es, existe una funcion computable ƒ y un polinomio p(X) tal que R(x) es computable en tiempo ƒ(κ(x)) ⋅ p(|x|).
3) Hay una función computable g: N → N tal que κ'(R(x)) < g(κ(x)).

Se tiene entonces que FPT es cerrada bajo reducciones fpt. Esto es, si un problema parametrizado (Q, κ) es reducible a un problema parametrizado (Q', κ') y (Q', κ') ∈ FTP, entonces (Q, κ) ∈ FPT.

Se escribe que (Q, κ) ≤^fpt (Q', κ'), si existe una reducción-fpt de (Q, κ) a (Q', κ').

Definamos [(Q, κ)]^fpt como la clase de problemas parametrizados reducibles-fpt a (Q, κ), esto es:
[(Q, κ)]^fpt := {(Q', κ') | (Q', κ') ≤^fpt (Q, κ)}

Si C es una clase de problemas parametrizados, se tiene [C]^fpt := ∪_{(Q, κ) ∈ C} [(Q, κ)]^fpt.

Por lo cual si (Q, κ) ≤^fpt (Q', κ') y (Q', κ') ∈ C entonces (Q, κ) ∈ C.

Y se define lo siguiente (como en teoria de complejidad clasica):

a) (Q, κ) es C-difícil bajo reducciones-fpt si todo problema en C es reducible-fpt a (Q, κ).
b) (Q, κ) es C-completo bajo reducciones-fpt si (Q, κ) ∈ C y (Q, κ) es C-difícil.

Clase para-NP

Se dijo que la clase FPT puede ser vista como una analogía de la clase PTIME, la pregunta es ¿existe una clase análoga a NP?. La clase resultante es la para-NP obtenida de reemplazar "algoritmo" por "algoritmo no determinista" de la definicion de FPT esto puede a ser algo no satisfactorio pero ayuda a aclarar algunas ideas. De la forma en que se define para-NP se pueden derivar clases parametrizadas de las clases de complejidad clasica ¹.

Un problema parametrizado (Q, κ) sobre Σ esta en para-NP, si existe una funcion computable ƒ:N→N y un polinomio p ∈ N₀[X], y un algoritmo no determinista tal que dado x ∈ Σ*, decide si x ∈ Q a lo más en ƒ(κ(x))⋅(p|x|) pasos.

Sea (Q, κ un problema parametrizado sobre un alfabeto Σ, entonces lo siguiente es verdadero:
1) (Q, κ esta en para-NP
2) "(Q, κ) esta en NP despues de una pre-computación sobre el parametro". Esto es, existie un alfabeto Π, una funcion computable π: N → Π* y un problema X ⊆ Σ* × Π* tal que X ∈ NP para todas las instancias x de Q tenemos

x ∈ Q ⇔ (x. π(κ(x))) ∈ X.

3) Q es decidible y "(Q, κ) es eventualmente en NP". Esto es, existe una funcion computable h: N → N u un algoritmo no determinista en tiempo polinomial que sobre la entrara x ∈ Σ* dedice si x ∈ Q en caso de |x| ≤ h(κ)).

Si bien esta definición no da una idea clara de la intratabilidad en el mundo parametrizado una vez mas nos reafrima que la parametrizacion es una relajación, lo que percibo hasta este punto es que la parametrización trata de atraer la intratabilidad a la tratabildad, pero la pregunta aqui es que es lo que hace que un problema parametrizado se acerque a la intratabilidad, esto tiene mucho que ver con su estructura y de ahi se deriva la clase W o mas bien la jerarquia W de la cual hablaremos en entradas siguientes, aun no se como tratar este tema, si dar una sola entrada tratando de ser lo mas entendible posible o dedicarle varias.

---

[1] Flum, G and Grohe, J . Describing parameterized complexity classes. STACS 2002.

Complejidad Descriptiva.

Hace más de 8 días, encontré unas diapositivas que ayudaron a aclarar mi ideas con respecto a la complejidad parametrizada, la idea general la tengo, pero cuando empecé a hacer la entrada del blog donde iba a empezar a hablar al respecto, tuve un problema. Para empezar a explicar acerca de este tema, tengo que describir dos problemas de los cuales uno no me quedaba claro, el "model checking", me di cuenta que esos capítulos del Papadimitriou a los cuales solo les había dado un vistazo debía estudiarlos a profundidad.

Encontré, si encontré - descubrí, cosas muy interesantes, ya antes había leido de lógica booleana, lógica de primer orden, de segundo orden; hasta hice todos los ejercicios de un libro de "introducción a la lógica". Pero la manera de ver la complejidad computacional después de leer detenidamente esos capítulos, que a veces ciertas frases parecen juegos de palabras o trabalenguas.

Ver los problemas computacionales desde la perspectiva de la lógica, es importante para la teoria de la complejidad. Por su naturaleza expresiva y versátil, no solo es usada para expresar la verdad matemática, si no también la computación a varios niveles.

Por una parte tenemos la lógica booleana (primer nivel) donde tenemos variables booleanas que pueden tomar dos valores de verdad, "verdadero" y "falso", estas se pueden combinar usando conectores booleandos como el "o lógico" (OR), el "y lógico" (AND), y el "no logico". Podemos tener expresiones booleanas llamadas literales, negaciones, conjunciones y disyunciones. Estos es solo la sintaxis, su estructura. Lo importate es su semántica, es decir, su significado. Hay ciertas expresiones "especiales" como la forma normal conjuntiva - CNF ¹ - (conjunciones de disyunciones) y la forma normal disyuntiva - DNF ²- (disyunciones de conjunciones). Lo importante en este nivel es definir la satisfactibilidad y la validez, dos propiedades muy importantes de las expresiones booleanas.

Un problema computacional que se puede tratar a este nivel es de SATIFACTIBILIDAD (o SAT), dada una expresión booleana en CNF, ¿es satisfactible? , de hecho este problema esta en NP exhaustivamente puede resolverse en O(n²2ⁿ). Un caso especial de SAT es el HORNSAT el cual esta en P.

Las expresiones booleanas puede representarse mediante circuitos (grafos) de aquí se desprende problemas como el CIRCUIT SAT y CIRCUIT VALUE los cuales están en NP y P respectivamente.

El siguiente nivel es la lógica de primer orden, aquí se introducen términos como constantes, funciones y relaciones que serán el vocabulario, hay implicaciones, equivalencias y cuantificadores (universal y de existencia). La asignación de verdad para la lógica de primer orden nos lleva a definir un modelo. Cuando se tiene una expresión sobre un vocabulario específico y tenemos un modelo apropiado para este vocabulario, se dice que el modelo satisface a la expresión. En mi caso que trabajo con grafos puse mucha atención a como se describen ciertas propiedades de los grafos en lógica de primer orden, como lo es la simetría, la transitividad, una función sobre el grafo por ejemplo que todos los nodos tengan grado uno, y en como se define un modelo. Este tipo de propiedades y funciones pueden verificarse en tiempo polinomial. Cada propiedad puede transformase en un problema computacional como: Dado un grafo G, ¿tiene cierta propiedad?, para este tipo de problemas se llega a la conclusión que están en P. Pero hay ciertos problemas computacionales que involucran grafos que son pueden ser expresado con lógica de primer orden como REACHABILITY. Para validar expresiones hay veces que hay que rebuscar un modelo que lo satisfaga, se dice entonces que la expresión es satisfactible, otras expresiones sin embargo son satisfactible por cualquier modelo, entonces decimos que la expresión es válida.

Hay ciertos teoremas que todavía me faltan por comprender, pero a grandes rasgos es lo mas importante que pude digerir. En el nivel de lógica de segundo orden, nos permite introducir propiedades como variables haciendo más fácil expresar problemas computacionales. Para cualquier expresión existencial en segundo orden que hacen referencia a grafos el problema esta en NP, si las expresión son cláusuas de Horn, el problema esta en P por ejemplo el problema del camino hamiltoniano.

Todo esto me llamo mas la atención cuando llegue a un enlace interesante. Aquí es donde viene lo importante y por lo cual he titulado a esta entrada "Complejidad Descriptiva".

La complejidad descriptiva, estudia que clases de complejidad computacional pueden ser caracterizadas por el "nivel" de lógica con el cuales se pueden expresar los lenguajes en ellas ³. Con los capítulos que leí acerca de esto y el enlace que encontré, me queda más claro como describir el problema que necesito explicar para abordar la complejidad parametrizada (entrada que deje inconclusa y no he publicado pues no me gusta publicar algo que no he entendido bien) y más adelante describir clases de complejidad parametrizada.

---

[1]. Conjuntive normal form
[2]. Disjuntive normal form
[3]. Descriptive Complexity

Clomplejidad Parametrizada

A manera de introducción, dos ejemplos.

En esta entrada, hago una breve introducción a los problemas parametrizados y la noción de la tratabilidad de parámetro fijo (fixed-parameter tractability).

Trabajaremos inicialmente con dos ejemplos, tenemos que tener en cuenta para ambos ejemplos el tamaño de la entrada n y un parametro k, al momento de hacer un análisis de comlejidad parametrizada.

Ejemplo 1: Evaluación de una consulta conjuntiva sobre una base de datos relacional, este tipo de consulta es la que más se presenta en la práctica, en términos de la teoría de complejidad clásica este problema es NP-completo, es decir, intratable.

Ejemplo 2: Verificación Automatizada: el problema aquí es que un sistema de estados finito (estructura Kripke), por ejemplo un circuito, cumpla con cierta propiedad, la propiedad es una formula φ en lógica temporal (LTL), y el problema es decidir si una estructura satisface la formula φ. Este problema es conocido como problema de verificacion del modelo LTL. Visto desde el punto de vista de complejidad clasica, este problema es intratable, es PSPACE-completo.

Estos dos problemas se prestan para hacer un análisis de su complejidad parametrizada. Lo mencione en la primera entrada, pero es bueno recordarlo una vez más, en la teoría de complejidad parametrizada, la complejidad de un problema no solo se mide por el tamaño de la entrada, si no también por un parámetro que se asume es pequeño. De esta manera la complejidad parametrizada tiene como objetivo clasificar problemas NP-duros dentro de otras "escalas" de manera que mucho problemas "duros" que requieren tiempo exponencial cuando su complejidad es medida en terminos del tamaño de la entrada, pero son computables con un parametro k pequeño como describiremos a continuación.

Los problemas arriba mencionados tienen consisten en dos partes cada uno y esas partes tienen tamaño diferente. En la práctica la base de datos y el espacio de estados son muy grandes, mientras que tanto la consulta como la formula tienden a ser pequeños. Como parámetros se eligen el tamaño de la consulta y el tamaño de la formula. Recordemos que tenemos a n es el tamaño de la entrada y k el parámetro. Ahora lo pondremos así:

Ejemplo 1:
n = tamaño de base de datos.
k = tamaño de la consulta.
Este problema se resuelve en O(n^k).

Ejemplo 2:
n = tamaño del espacio de estados.
k = tamaño de la formula.
Este problema se resuelve en O(k 2^2k n).

Si observamos estos dos problemas tienen tiempo de ejecución exponenciales y ambos son polinomiales, para un k fijo (recordar que k es pequeño en comparación de n). Si k = 5, para O(n^k) puede ser un valor extremadamente alto llevaria a un tiempo de computo excesivo, mientras que para el factor 2^2k en O(k 2^2k n) puede llegar a ser desagradable pero aceptable para el problema que sabemos que es PSPACE-completo. Se dice que el problema de verificar el modelo LTL es fixed-parameter tractable (tratable con parametro fijo). La pregunta a resolver sería si el problema de evaluar una consulta conjuntiva es fixed-parameter tractable, es decir, si existe un problema similar al algoritmo del problema de verificar el modelo LTL.




En este caso es necesario observar que las bases de datos suelen ser muy grandes mientras en la practica las consultas tienden a ser pequeña. La evaluación de una consulta de una base de datos puede resolverse en O(n^k, si bien este tiempo es exponencial, notese que el parametro es polinomial para una valor k fijo.

Problemas parametrizados

Hay que recordar que los problemas de decisión se describen como lenguajes sobre alfabetos finitos Σ. Para distinguirlos de los problemas parametrizados, nos referiremos como conjuntos Q ⊆ Σ^* sobre cadenas de Σ

Sea Σ un alfabeto finito:
1) Una parametrizacion de Σ^* es un mapeo κ: Σ^* → N, que es computable en tiempo polinomial.
2) Un problema parametrizado es un par (Q,κ) cque consiste en un conjunto Q ⊆ Σ^* sobre cadenas de Σ y una parametrizacion κ de Σ^*.

Siempre se representara un problema parametrizado de la siguiente forma:

Instancia: x ∈ Σ^*.
Parametro: κ(x)
Problema: Decidir si X ∈ Q.

Ejemplo: Sea SAT el conjunto de todas las formula proposicionales satisfactibles, donde las formulas son codificafas como cadenas sobre un lenguaje finito Σ y sea κ: Σ^* → N una parametrización definida como: κ(x) es igual al numero de variables de x, si x es una formula proposicional o es igual a 1 en otro caso, entonces el problema SAT parametrizado (p - SAT) se puede representar de la siguiente forma:

p-SAT
Instancia:Una formuala proposicional α
Parametro: κ(x)
Problema: Decidir si α es satisfactible.

Tratabilidad con parametro fijo

Sea Σ un alfabeto finito y κ: Σ^* → N una parametrización
1) Un algoritmo con alfabeto de entrada Σ es un algoritmo-ftp con respecto a κ si existe una funcion computable ƒ: N → N y un polinomio p ∈ N₀[X] tal que para cada x ∈ Σ^* el tiempo de ejecución es a lo más:

ƒ(κ(x) p(|x|)

2) Un problema parametrizado (Q, κ) es tratable con parametro fijo, si existe un algoritmo-ftp con respecto a κ que decida Q.

FTP denota a la clase de todo los problemas tratables con parametro fijo.


Por ejemplo: el problema p-SAT es tratable con parametro fijo, el algoritmo de busqueda por fuerza bruta decide una formula φ de tamaño m con k variables en tiempo O(2^k m).

Si Q ∈ PTIME, entonces (Q, κ) ∈ FTP para cada parametrización κ Se tiene entonces que la tratabilidad con parametro fijo relaja la noción clásica de tratabilidad, la decibilidad en tiempo polinomial, un claro ejemplo es el problema de vericacion de modelo LTL.

Clases de Complejidad, parte III

En la entrada anterior se describió como se define una clase de complejidad, en términos de maquinas de Turing y lenguajes recordaremos unas definiciones que ampliaremos.

Dada una función ƒ(n), se consideran las clases de complejidad siguientes:

• Clase TIME(ƒ(n)) es el conjunto de lenguajes L tales que una máquina de Turing determinista decide en tiempo ƒ(n).
  
• Clase NTIME(ƒ(n)) es el conjunto de lenguajes L tales que una máquina de Turing no determinista decide en tiempo ƒ(n).
  
• Clase SPACE(ƒ(n)) es el conjunto de lenguajes L tales que una máquina de Turing determinista decide usando un espacio ƒ(n).
  
• Clase NSPACE(ƒ(n)) es el conjunto de lenguajes L tales que una máquina de Turing no determinista decide usando un espacio ƒ(n).
  

Ahora bien en base a la familia de funciones parametrizadas por un entero k>0, que acotan el recurso, en esta caso el tiempo, podemos definir las siguientes clases:

• Clase P es el conjunto de lenguajes L tales que una máquina de Turing determinista decide en tiempo polinomial TIME(ƒ(n^k)).
  P = ∪_k>0 TIME(ƒ(n^k)).
  
• Clase NP es el conjunto de lenguajes L tales que una máquina de Turing no determinista decide en tiempo polinomial NTIME(ƒ(n^k)).
  NP = ∪_k>0 NTIME(ƒ(n^k)).
  
• Clase EXP es el conjunto de lenguajes L tales que una máquina de Turing determinista decide en tiempo polinomial TIME(ƒ(2^nk)).
  
• Clase NEXP es el conjunto de lenguajes L tales que una máquina de Turing no determinista decide en tiempo polinomial TIME(ƒ(2^nk)).
  

Ahora definiremos las clases en base a la familia de funciones el espacio:

• Clase PSPACE es el conjunto de lenguajes L tales que una máquina de Turing determinista decide usando un espacio SPACE(ƒ(n^k)).
  P = ∪_k>0 TIME(ƒ(n^k)).
  
• Clase NPSPACE es el conjunto de lenguajes L tales que una máquina de Turing no determinista decide usando un espacio NSPACE(ƒ(n^k)).
  NP = ∪_k>0 NSPACE(ƒ(n^k)).
  
• Clase L es el conjunto de lenguajes L tales que una máquina de Turing determinista decide en tiempo polinomial SPACE(ƒ(log n).
  
• Clase NL es el conjunto de lenguajes L tales que una máquina de Turing no determinista decide en tiempo polinomial NSPACE(ƒ(log n)).
  

Hay una serie de inclusiones entre las distintas clases de complejidad:
SPACE(ƒ(n)) ⊆ NSPACE(ƒ(n)),
TIME(ƒ(n)) ⊆ NTIME(ƒ(n)),

Se han dedicado muchos esfuerzos a estudiar las relaciones entre clases de complejidad diferentes, y todavía quedan problemas abiertos como P = NP? o P ≠ NP?.

Se tiene claro P ⊆ NP, pero no se ha conseguido aún demostrar ni que P = NP ni lo contrario, que P ≠ NP. Para demostrar la primera, P = NP, sería necesario demostrar que todo problema de NP puede resolverse con una máquina de Turing determinista en tiempo polinomial. Y para demostrar la segunda, P ≠ NP, habría que encontrar un problema NP que no esté en P, un problema para el que exista una maquina de Turing no determinista de complejidad en tiempo polinomial para el que nunca pueda encontrarse uno determinista de la misma complejidad.

Algo que puede causar ruido es se ha demostrado que PSPACE = NPSPACE, un resultado que suguiere fuertemente que el no determinismo es menos poderoso con respecto al espacio que con respecto al tiempo. Con esta información podemos hacer las siguientes inclusiones:

L ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE.

Ahora bien a continuación definiremos dos conceptos muy importantes en la teoría de la complejidad: reducción y completitud.

Reducciones.

Las clases de complejidad contiene un conjunto infinito de lenguajes, por ejemplo la clase NP contiene problemas como TSP, SAT, CLIQUE, entre otros. No todos los problemas en la misma clase son igualmente dificiles, para establecer un orden de problemas de acuerdo a su dificulta, se proponen las reducciones. Un problema A es por lo menos tan difícil como otro problema B si existe una reducción del problema B al problema A.

Decimos que el problema B se reduce al problema A si existe una transformación R tal que, por cada entrada x de B, produce una entrada equivalente y de A, es decir y = R(x) . El término equivalente quiere decir que la respuesta a R(x) considerada como entrada para B es una respuesta correcta a y considerada como entrada para A. En otras palabaras, para resolver B por la entrada x sólo hay que construir R(x) y resolver A. Si contamos entonces con un algoritmo para el problema A y un algoritmo para construir R(x) la combinacion de ambos nos da un algoritmo para resolver B.

Aqui es importante que la reducción es facil de construir, en pocas palabras, las reducciones tambien se clasifican según los recusos que se usen, por ejemplo las reducciones de Cook permite que R(x) sean computadas por una máquina de Turing en tiempo polinomial y reducciones de espacio logarítmico. Poniendolo en terminos de lenguajes, se tiene:

Un lenguaje L es reducible a un lenguaje L′ , denotado por L ≤_L L′ , si y sólo si existe una función R de cadenas a cadenas que está computada por una máquina Turing determinista en espacio O (log n) tal que para toda entrada x

x ∈ L si y sólo si R(x) ∈ L′

La función R se llama una reducción de L a L′ .

Completitud

La transitividad de la reducción polinómica nos dice que es una relación de equivalencia, y la relación ≤_L impone un orden parcial en las clases de equivalencia de problemas resultantes, es decir, nos ordena los problemas segun su complejidad. De hecho, la clase P forma la “menor” clase de equivalencia con este orden parcial y, por tanto, puede verse como la clase que contiene los problemas de decisión computacionalmente “más fáciles”. Definiremos ahora que es completo.

Sea C una clase de complejidad, y sea L un lenguaje que pertenece a C, A ∈ C. Diremos que L es C-completo si todo lenguaje L’ ∈ C se puede reducir a L, L' $le; _L.

Otra definición importante es: Un lenguaje es C-dificil si se puede reducir cada lenguaje L’ ∈ C a L, pero no se sabe si es válido que L ∈ C.

Con estos conceptos ya definidos, creo estar lista para en la siguiente entrada hablar de la teoría de complejidad parametrizada, en su momento definiré a fondo otros conceptos que tal vez he pasado por alto, pero serán más fáciles de digerir, si tenemos entendidos estos conceptos, ya sea que dedique una entrada completa o solo haga comentarios en entradas ya publicadas.

---

Clases de Complejidad, parte II

Por mucho mucho tiempo se han resuelto tareas de cómputo de muchas maneras y mediante muchos dispositivos desde un abaco hasta la moderna computadora, la pregunta es: ¿Que modelo matemático captura todas las maneras de hacer cómputo? La respuesta es: La máquina de Turing ¹ la cual es un modelo simple pero suficiente para estudiar muchos aspectos de la computación como su eficiencia.

La máquina de Turing es una simple estructura de datos, una cadena de símbolos (cinta); las operaciones permitidas (efectuadas por un "cabezal") son: leer un símbolo de la cadena, moverse hacia la izquierda o derecha y escribir un nuevo símbolo en la posición actual o "expandirse" como explicaremos más adelante, las operaciones a realizar se basan en un conjunto de "reglas". Este modelo es simple pero es capaz de expresar cualquier algoritmo.

Formalmente una máquina de Turing es una tupla M = (Q, Σ,δ, q₀) donde:
Q: es un conjunto finito de estados.
Σ: es un conjunto finito de simbolos, simpre contiene el simbolo en blanco ⌊⌋ y el símbolo de "comienzo" ►.
δ: es una función de transición que mapea Q × Σ → ( Q ∪ {h, "si", "no"}) × Σ × {← (izquierda) ,→ (derecha), - (no moverse)}.
q₀: es el estado inicial q₀ ∈ Q.

Se asume que el estado h es estado de paro (halt), "si" es el estado de aceptación y "no" el estado de rechazo. En pocas palabras δ es una regla que especifica para cada combinación de un estado actual q ∈ Q y un simbolo actual σ ∈ Σ una transición a un estado p, un símbolo ρ se sobreescribe en σ y el cursor se mueve hacia una dirección o se queda en la posición actual, esto es δ(q, σ) → (p, ρ D), donde D = {←, →, - } son las direcciones a las cuales se puede mover el cursor (cabezal que lee los símbolos).

El cabezal siempre realiza una acción hasta que se alcanza algun estado de paro como {h, "si", "no"}) Si es asi se dice que la maquina ha parado (halted). Si el estado "si" se alcanza se dice que la máquina acepta la entrada (la cadena de simbolos), si se alcanza el estado "no" se dice que la máquina rechaza la entrada. Si h se ha alcanzado la salida es la cadena de M al tiempo de paro, la cadena de salida en este caso se denota como y.

Si M acepta o rechaza la entrada x entonces M(x) = "si" o "no" respectivamente. Si se alcanza h, M(x) = y, Si M nunca llega a un estado de paro con la cadena x se escribe M(x) = "↗". En la siguiente figura se muestra en la parte izquiera una máquina de Turing y en la parte derecha se muestra la computación, M simplemente inserta un espacio en blanco entre el símbolo de inicio y la cadena de entrada. Cada operación de la maquina de Turing se define como configuración.



Cuando se va de una configuración a otra se dice que se ha dado un paso en el ejemplo de la figura anterior de la configuración inicial a la final se dieron 15 pasos. Hasta este punto se ha descrito a grandes rasgos que es una máquina de Turing, como "funciona" y unos conceptos básicos, ahora profundizaremos en ciertos conceptos que son muy necesarios para la definición de clases de complejidad.

Máquinas de Turing como algoritmos

Las máquinas de Turing son ideales para resolver cierto tipos de problemas especializados sobre cadenas, como aceptar o decidir "lenguajes". A continuación se listarán una definiciones de utilidad:

Sea L ⊂ (Σ - {⌊⌋})* un lenguaje, es decir, un conjunto de cadenas de simbolos. Sea M una máquina de Turing tal que para cada cadena x ∈ (Σ - {⌊⌋})*. Decimos que M decide L si y solo si x ∈ L, entonces M(x) = "si" y si x ∉ L then M(x) = "no". Si M decide L entonces L es llamado un lenguaje recursivo.

Una máquina Turing acepta un lenguaje L si para toda sucesión x ∈ (Σ - {⌊⌋})* aplica que si x ∈ L, M(x) = “si", pero si x ∉ L, M(x) ="↗". Los lenguajes aceptados por alguna máquina Turing son recursivamente numerables. Nota que si L es recursivo, también es recursivamente numerable.

Las funciones computables son el objeto básico de estudio de la teoría de la computabilidad y consisten en las funciones que pueden ser calculadas por una máquina de Turing. Suponga que ƒ es una función de x ∈ (Σ - {⌊⌋})* a Σ* y sea M una maquina de Turing con alfabeto Σ Desimo que M computa a ƒ si para cualqueir cadena x ∈ (Σ - {⌊⌋})*, M(x) = ƒ(x). Si tal M existe, ƒ es llamada una función recursiva.

Maquinas de Turing con multiples cadenas.

Para definir formalmente el tiempo y el espacio requerido por una máquina de Turing para hacer computaciones, se debe introducir una generalización de esta, la máquina de Turing con multiples cadenas o más bien máquina de Turing con k cadenas, donde k >= 1. La máquina se define como anteriormente se hizo, la función de transición decide el siguiente estado igual que antes, solo que ahora decide para cada cadena el símbolo a escribir y la dirección del cabezal viendo el estado y símbolo actual de cada cadena. La salida de la computación de una máquina de Turing de k-cadenas con entrada x es como en la descirta anteriormente (k=1) con la sola diferencia que la salida se lee del última cadena cuando la máquina se detiene. La configuración y el número de pasos se define análogamente a como se definio anteriormente.

Ahora viene lo más importante, si para una maquina con k cintas se llega de una configuración incial a una configuración de paro en t pasos, entonces el tiempo requerido por M sobre la entrada x es t. Es decir, el tiempo requerido es simplemente el número de pasos para parar. Si M(x) ="↗" entonces el tiempo requerido por M sobre x es infinito.

Sea ƒ una función de N a N. Decimos que la maquina M opera con tiempo ƒ(n) para cualquier entrada x, el tiempo requerido por M sobre x es a lo más ƒ(|x|). Supongamos que un lenguaje L ⊂ (Σ - {⌊⌋}) es decidido por una máquina de Turing multicadena en tiempo ƒ(n). Se dice que L ∈ TIME(ƒ(n)). Esto es TIME(ƒ(n)) es un conjunto de lenguajes que pueden ser decididos por máquina de Turing multicadenas que operan con un tiempo acotado por ƒ(n). TIME(ƒ(n)) es una clase de complejidad de tiempo, pero tambien tenemos clases de complejidad de espacio.

Cuando la máquina de Turing para, el cabezal se detiene en cierta posición de la última cinta, denotemos w como la parte izquierda de la cadena tomando en cuenta el simbolo sobre el cual esta el cabezal y u la parte de la cadena a la derecha del cabezal. Entonces el espacio requerido por M es Σ_i=1^k-1|w_iu_i|. Supongase ahora que ƒ es una funcion de N a N. Entonces decimos que una máquina de Turing M opera en un espacio acotado por ƒ(n). Sea L un lenguaje, decimos que L estan en la clase de complejidad de espacio SPACE(ƒ(n)) si existe una máquina de Turing con entrada y salida que decida L y opere en un espacio acotado por ƒ(n).

Maquinas no deterministas

Una máquina no determinista es una tupla M = (Q, Σ,Δ, q₀) donde Q, &Sigma y σ se definen de igual manera que lo hicimos anteriormente, salta a la vista la diferencia, en una máquina no determinista no tiene una sola acción siguiente definida, si no una opción de acciones, Δ no es una función es una relación &Delta ⊂ (Q × Σ) × [( Q × ∪ {h, "si", "no"}) × Σ × {←, →, -}. Esto es para cada combinacion de estado símbolo hay más de una acción a realizar o ninguna.

Una entrada es aceptada si hay mas de una secuencia de opciones no determinadas que resulten en "si". Otras opciones podrían resultar en rechazo, solo una computación aceptable es suficiente. La cadena es rechazada sí y sólo sí no hay secuencias de opciones puede conducir a aceptar la cadena.

Decimos que una máquina N decide un lenguaje L en tiempo ƒ(n), si N decide L y hay k cantidad de pasos de una configuración incial a una configuracion de paro, entonces k <= ƒ(|x|). Esto es, se requiere que N, ademas de aceptar a L, no tengas rutas de computación mas grandes que ƒ(n). El conjunto de lenguajes decididos por una máquina de Turing no determinista en tiempo ƒ es la clase de complejidad NTIME(ƒ(n)).

---

[1] Turing, A.M. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2, 42, 230-265. 1936.

Clases de Complejidad, parte I

Como se mencionó en la sesión anterior, para comprender la teoría de complejidad parametrizada hay que tener bases de la teoría de complejidad computacional clásica, en la sesión pasada, se introdujo al lector en el tema, en esta sesión se profundizará en los parámetros que definen una clase de complejidad. Empezaremos por abordar como definir funciones para acotar el recurso que se desea medir.


Análisis de Algoritmos
La teoría de complejidad estudia la cantidad de recursos (tiempo de cómputo y el espacio en memoria) utilizados para resolver un problema, ahora bien, las preguntas son: ¿Cómo medir esos recursos?, ¿Cuál es el tiempo máximo que debo esperar para tener la solución a un problema?. Nos enfocaremos a describir como estimar teóricamente el tiempo que necesita un algoritmo para resolver el problema.

Cantidad de trabajo realizado

Típicamente se mide la eficiencia computacional de un algoritmo como el número de operaciones básicas que realiza en función del tamaño de la entrada. Generalmente para analizar un algoritmo se aisla una operación especifica que sea fundamental para el problema que se estudia. Por ejemplo, para el problema de ordenar un arreglo, las operaciones básicas serían las comparaciones. En medida que las operaciones basicas se eligan bien se tendrá una buena medida del trabajo realizado.

Ahora bien la cantidad de trabajo realizado no se puede describir solo con un número porque el número de pasos no es el mismo con todas las entradas, por esto queda claro que la medida esta en función de tamaño de la entrada y además de la "naturaleza de la entrada", por ejemplo un algoritmo para ordenar números, podría efectuar poco trabajo si esos números estan parcialmente ordenados en comparacion si estan totalmente desordenados que sería el peor caso. Casi siempre se describe el comportamiento de un algoritmo dando su complejidad del peor caso. Tenemos entonces que: "La complejidad el peor caso es el número máximo de operaciones básicas que el algoritmo ejecuta con cualquier entrada de tamaño n"

Al asociar una unidad de tiempo a cada operación básica, se tendrá el tiempo de computo T(n) y es de interes particular calcular su "complejidad" en sentido asintótico, es decir, para un tamaño de entrada suficientemente grande cuando n tiende a infinito.

Comportamiento asintótico

Cuando se estudia el comportamiento asintotico, se estudia la velocidad de crecimiento de T(n) conforme el tamaño de la entrada (instancia) aumenta. Para ello se asocia a T(n) funciones f(n ) que caracterizan su comportamiento. Es de interés en esta parte hablar de la notación O (O grande).

Definición 1 Sean f(n) y g(n) funciones de N a R:

(a) f(n) = O(g(n)) si existe una constante c > 0 tal que para una número grande de n, f(n) <=cg(n). Se tiene entonces que g(n) es una cota superior.

(b) f(n) = Omega(g(n)) si existe una constante c > 0 tal que para una número grande de n, f(n) >=cg(n). Se tiene entonces que g(n) es una cota inferior.

(c) f(n) = Theta(g(n)) si existe una constante c > 0 tal que para una número grande de n, f(n) =O(g(n)) y f(n) = Omega(g(n))

Por lo tanto la notación O(f(n)) nos dice que el tiempo de computo de un algoritmo esta a lo más caracterizado por f(n), y esta es la cota que nos interesa estudiar cuando se habla de complejidad computacional. Siempre se preferiran funciones polinomicas o de orden inferior a funciones exponenciales o factoriales. Para tener una idea clara de esto se presenta la siguiente tabla, donde Funcion, se refiere a la funcion del tiempo en segundos.

Tamaño de la entrada n
Función	10	100	1000
n	10	100	1000
n log n	33	664	9966
n^3	1000	1000000	10^9
10^6 * n^8	10^14	10^22	10^30
2^n	1024	1.27 x 10 ^30	1.05 X 10 ^301
n ^(log n)	2099	1.39 X 10^13	7.89 x 10 ^29
n!	3,628,800	10^158	4 X 10 ^2567

Dejo al lector, realizar las conversiones a minutos, días y años, ponga atención al tiempo que se llevaría resolver un problema con un algoritmo que tienen comportamiento exponencial O(2^n). Algunas lecturas recomendadas para profundizar en el tema son:

[1] Baase, Sara. Computer Algorithms: Introduction to Design and Analysis. Addison-Wesley.
[2] Johnsonbaugh, Richard. Discrete Mathematics . Prentice Hall.

En la parte 2 de este tema abordaremos los modelos de computo y el modo de hacer computo, para en la parte 3, empezar a definir clases de complejidad y posteriormente definir términos de complejidad parametrizada.

Teoría de Complejidad Parametrizada, una breve introducción.

Si buscamos en Google "Complejidad Computacional" encontraremos que es una rama de la Teoría de la Computación que se encarga de clasificar problemas computacionales de acuerdo a su dificultad. Donde definen problema computacional como una tarea que se resuelve a través de una computadora.

En la teoría de complejidad computacional [1], los "problemas computacionales" que se abordan son problemas llamados problemas de decisión, es decir, problemas que requieren como respuesta "si" o "no". Por ejemplo: ¿Dado un grafo G = (V, E), se puede colorear con k colores? ¹. Lo que realmente es de interés son los algoritmos que pueden decidir - resolver - nuestros problemas, en sí, nos interesa que tan difícil es resolver el problema y para ello de alguna manera se mide la cantidad de recursos (ya sea tiempo de cómputo o espacio en memoria) requeridos para resolver el problema. Por lo regular se mide el tiempo de cómputo o el espacio requerido en función del tamaño de la instancia ² del problema a resolver. En el caso de los grafos el tamaño de la instancia es el número de nodos.

Para poder clasificar un problema dentro de una clase de complejidad. Una clase de complejidad está especificada por algunos parámetros (de los cuales trataremos en próximas sesiones) como son:

1. Un modelo de cómputo, tal como una Máquina de Turing.
   
2. El modo de hacer el cómputo. Determinista o No determinista.
   
3. El recurso que se desea medir (acotar). Tiempo o espacio.
   
4. Y una función que define una cota tomando como parámetro el tamaño de la instancia.
   

Por lo regular nos interesa que la tasa de crecimiento de las funciones que definen la cota en función del tamaño de la instancia sea polinomial , esto nos indica requerimientos de tiempo de cómputo aceptables, en contraste las tasas de crecimiento exponenciales causan preocupación y podríamos llegar a decir que el problema es intratable, es decir, no tener una solución práctica. Tal es el caso de los problemas que pertenecen a la clase NP-completo, es decir, para estos problemas el tiempo requerido para resolver el problema usando cualquier algoritmo conocido se incrementa rápidamente con el tamaño de la instancia, para versiones algo grandes de instancia del problema podría llevarse millones de años conocer la solución usando el poder de cómputo actual, lo que no es nada práctico.

Ahora que hemos dado una pequeña introducción acerca de la teoría de complejidad computacional "clásica", podemos hablar de la teoría de complejidad parametrizada [2], en la cual, es de interés definir una cota en función del tamaño de la instancia y un parámetro del problema.

Se habla entonces de parametrizar el problema, por ejemplo en el problema de coloreo de grafos, nos interesa aparte del tamaño del grafo, el parámetro k. Es bien sabido que el problema de 3-coloreo (colorear un grafo solo con tres colores) es NP-completo, así como mucho problemas más [3], la idea de parametrizar un problema es que si sabemos que el problema es NP-completo o intratable, en algunos casos solo un pequeño rango de parámetros son realmente importantes en la práctica, lo cual los hace "tratables" dentro de esos rangos, lo cual nos da una idea más optimista acerca de la solución del problema.

Para todo aquel que desee más información acerca del tema o seguir mi blog se recomiendan los siguientes libros:
[1] Papadimitriou, Christos (1994). Computational Complexity (1st ed.). Addison Wesley.
[2] Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer.
[3] Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman.

Conforme vaya creciendo este blog pondré enlaces a literatura interesante que he encontrado. En próximas sesiones abordare mas específicamente temas de complejidad computacional "clásica" que harán mas digerible la teoría de complejidad parametrizada. La idea de mi proyecto doctoral es definir la complejidad computacional en términos no sólo del tamaño de la instancia si no de alguna propiedad estructural de la instancia. Espero sus comentarios.

---

¹ Colorear un grafo se refiere a asignar un color a cada nodo con la restricción que dos nodos adyacentes no pueden tener asignado el mismo color.
² Por instancia del problema, se refiere cuando damos valores a los parámetros del problema, por ejemplo para el coloreo de grafo una instancia del problema es: un grafo con |V| = 5 nodos, |E| = 10 aristas, que se desea colorear con k =3 colores.