Computación humana para automatización de diseño electrónico

El artículo que describe el trabajo del que hablábamos hace algo más de una semana sobre la resolución del instancias de SAT mediante un juego está ya disponible online. Se trata de

• Human computing for EDA [pdf]

de Andrew DeOrio y Valeria Bertacco. El artículo es muy corto, sólo dos páginas, y no proporciona muchos más detalles acerca del sistema. Sí menciona algún aspecto de interés, como es el hecho de que la disposición espacial de las cláusulas intenta corresponderse con las variables que la afectan (lamentablemente no entra en detalles sobre cómo  han atacado este extremo, ya que es un problema de optimización geométrica muy interesante).

Con todo, lo más relevante del artículo sean las referencias a la escalabilidad (que ya anticipamos el otro día como uno de los cuellos de botella del enfoque). Al parecer, la idea básica es que cada nivel sea una visión local de una parte del problema completo, visión que se irá ampliando al ir aumentando de dificultad. En instancias de gran tamaño sugieren emplear un enfoque multi-jugador en el que cada participante juega sobre una parte del problema. Obviamente hay interrelaciones entre estas partes (si modificamos una variable podemos alterar el estado de una cláusula de otro tablero), por lo que la división debería hacerse de manera astuta de forma que estas interrelaciones sean mínimas. La mala noticia es que tendríamos entonces un problema de corte mínimo en grafos, que es NP-hard si se introducen restricciones sobre el número de interrelaciones entre subconjuntos.

Resuelve problemas NP-completos mientras juegas

La clase NP -de la que ya hemos hablado en alguna ocasión- abarca aquellos problemas de decisión que pueden resolverse en tiempo polinómico no determinista, o lo que es lo mismo, aquellos problemas para los que es posible verificar en tiempo polinómico la validez de una solución dada. Esta clase ha sido tradicionalmente empleada como sucedáneo de la idea de intratabilidad computacional. No se trata de la mejor caracterización, ni siquiera de la más apropiada, puesto que admite mucha patología y en ocasiones tiene un impacto práctico limitado, pero eso será tema de algún futuro post. Sea como fuere, es común que allá donde nos enfrentemos a un problema NP-hard se emplee este hecho como justificación para el empleo de algún tipo de (meta)heurística.

Nuestra comprensión sobre cómo aplicar metaheurísticas para resolver problemas específicos ha avanzado enormemente en la última década. Una de las claves está en ser capaces de explotar conocimiento del problema durante el proceso de búsqueda. Técnicas tales como los algoritmos meméticos se basan fundamentalmente en esta idea. Evidentemente no se trata de algo trivial de conseguir, y aquí es donde es posible que la mente humana eche una mano y no en la ingeniería del proceso sino contribuyendo capacidad de búsqueda pura y dura. No se trata por supuesto de cálculo numérico ni de búsqueda sistemática, sino de explotar algunas de las cualidades que nuestros cerebros han ido desarrollando durante millones de años de evolución: estrategia y procesamiento visual.

La capacidad de extraer información de un torrente de datos visuales es una de nuestras grandes bazas. Estamos programados para buscar orden en el caos, patrones en el ruido blanco, formas conocidas en el desorden. Áreas tales como la minería de datos visual intentan explotar precisamente esta característica. Por otra parte nuestra visión estratégica, la capacidad de trazar planes y seleccionar heurísticamente las ramificaciones más relevantes es también bien conocida en el ámbito -por ejemplo- de los juegos de tablero. Es precisamente en este área en el que investigadores de la Universidad de Michigan han intentado aunar ambas capacidades y dirigirlas hacia la resolución de problemas NP-completos. Andrew DeOrio y Valeria Bertacco, del departamento de ingeniería eléctrica e informática de la citada universidad, han desarrollado un entorno en el que se pueden resolver instancias del problema de la satisfacibilidad lógica mediante un juego lejanamente relacionado con el clásico lights off.

FunSAT - Pulsa sobre la imagen para jugar

En el tablero tenemos una matriz de burbujas que representan las cláusulas de la instancia del problema (esto es, las restricciones que debemos satisfacer). Estas cláusulas dependen de un conjunto de variables, representadas como rectángulos en los bordes del tablero. Pulsando sobre éstos podemos fijar una cierta variable a cierto/falso o dejarla indefinida. De resultas de cualquiera de estas acciones algunas cláusulas pasarán a estar satisfechas (lo que se indicará mediante el color verde) o insatisfecha (un tono grisáceo, tanto más oscuro cuantas menos variables que puedan afectar a dicha cláusula nos queden sin asignar). El tamaño de cada burbuja indica el número de variables que intervienen en ella (se puede jugar también a 3-SAT, variante clásica en la que todas las cláusulas tienen 3 variables involucradas).

Lo interesante es que las instancias de SAT que se plantean en este juego corresponden supuestamente a problemas de diseño VLSI.  El análisis de lo que el juego puede dar de sí lo han publicado en un artículo titulado

• Human computing for EDA

que presentarán en la próxima Design Automation Conference, que se celebra en San Francisco en estos días. El artículo aún no está disponible, por lo que se puede añadir poco más a lo ya comentado. Esperaremos a leerlo para ver cuál es el planteamiento a largo plazo del invento, que a priori diríase que adolece de un problema de escalabilidad. Y es que el ser humano es extraordinario, pero dentro de un límite.

La clase PP, computación democrática, y la cota de Chernoff

Hace tiempo hablamos de las clases de complejidad P y NP a cuento de la computación cuántica, y aunque sin duda estas dos clases son las más conocidas (incluso fuera del ámbito de la informática teórica) no son ni muchísimo menos las únicas. Hay todo un universo de diferentes clases que habitan tanto en el interior de P o de NP, como en su exterior, englobando a estas dos en parte, o totalmente. Esto último es precisamente el caso de la clase que nos ocupa: PP (Probabilistic Polynomial-Time). Antes de definirla, recapitulemos brevemente el significado de P y NP. Estamos considerando problemas de decisión, para los que la respuesta es SÍ o NO. Si tenemos un algoritmo que en un número polinómico de pasos (esto es, un número p(n) -donde n es el tamaño del problema- tal que asintóticamente p(n) < an^c, donde a y c son dos constantes) es capaz de solucionar correctamente el problema, entonces dicho problema está en la clase P. Por otra parte, consideremos un programa no-determinista que en ciertos momentos lanza monedas al aire y toma decisiones al azar. Si dado un problema, siempre que la respuesta es SÍ existe al menos una secuencia de decisiones tales que el algoritmo anterior responde SÍ en tiempo polinómico, y siempre que la respuesta es NO, todas las secuencias de decisiones resultan en un NO, entonces el problema está en la clase NP. Análogamente, si siempre que la respuesta es NO, existe al menos una secuencia de decisiones tales que el algoritmo responde NO en tiempo polinómico, y siempre que la respuesta es SÍ, todas las secuencias de decisiones resultan en un SÍ, entonces el problema está en la clase co-NP. Un ejemplo de problema en NP (y de hecho, NP-completo) es el de la satisfacibilidad (SAT): dada una fórmula lógica, ¿existe una asignación de valores de verdad a las variables que la componen, tal que la fórmula sea cierta? Si en lugar de SAT consideramos VALIDITY (dada una formula lógica, ¿es cierta para todas las asignaciones de valores de verdad a las variables que la componen?), tenemos un problema en co-NP (y de hecho, co-NP-completo). Se sabe que P está contenido en NP ∩ co-NP, y se cree que la inclusión es estricta, y que NP ≠ co-NP.

Una vez definido lo anterior, podemos describir la clase PP como la colección de todos los problemas para los que si la respuesta es SÍ un algoritmo no-determinista da la solución correcta en tiempo polinómico y con probabilidad superior al 50%. Si nos imaginamos que el algoritmo no-determinista toma sus decisiones aleatorias de manera uniforme, esto quiere decir que la decisión mayoritaria de todas las ramas de computación es la correcta (motivo por el cual se ha propuesto también la denominación Majority-P). Por ejemplo, consideremos el problema MAJSAT: dada una fórmula lógica, ¿tiene más asignaciones de verdad que la hacen cierta que asignaciones que la hacen falsa? Un algoritmo que genere una asignación de verdad uniformemente al azar y compruebe si hace cierta o falsa la fórmula responderá SÍ con probabilidad mayor al 50% si y sólo si hay más asignaciones que hagan la fórmula cierta, que asignaciones que la hagan falsa.

En relación con las clases mencionadas anteriormente es fácil ver que NP está contenida en PP. Para ello, considérese el problema SAT y un algoritmo que genere una asignación al azar, y si hace cierta la fórmula responda SÍ, y si la hace falsa responda SÍ o NO al 50%. Si la formula no es satisfacible, el SÍ y el NO ocurrirán con el 50% de probabilidad, pero si es satisfacible, la probabilidad será superior. ¿Cuánto superior? Si las asignaciones de calculan al azar, y hay N asignaciones que hacen cierta la fórmula, la probabilidad del SÍ será p=1/2+N2^-n, donde n es el número de variables lógicas. La utilidad de que la probabilidad sea estrictamente mayor al 50% radica en el hecho de que al repetir la ejecución del algoritmo múltiples veces, se amplifica la probabilidad de que salga SÍ (si la respuesta es efectivamente esa). Obviamente, cuanto menor sea el margen por el que se supera el 50%, serán necesarias más ejecuciones del algoritmo para aumentar la probabilidad de que la solución que ha salido más veces sea la correcta. La cota de Chernoff nos dice cuántas ejecuciones tenemos que hacer para que la probabilidad de que respuesta mayoritaria sea incorrecta esté por debajo de un cierto ε. Concretamente, dicho número k es

En el ejemplo anterior de SAT, en el caso extremo en el que N=1, tendríamos que el número de ejecuciones para un cierto ε sería

esto es, exponencial en el tamaño del problema. Esto hace que en el fondo un algoritmo de este tipo no sea práctico. Si el margen por el que se supera el 50% resulta sin embargo no ser exponencialmente pequeño en n, sino constante, tendríamos un algoritmo mucho más útil, y también una clase de complejidad diferente, de la que hablaremos otro día.

    

Lo que la computación cuántica (no) puede hacer por nosotros

Hoy es el día en el que los muchachos de D-Wave planean hacer la presentación de su sistema cuántico Orión, tal como Alvy nos acaba de recordar en Microsiervos. Creo que puede ser entonces interesante analizar someramente qué es lo que la computación cuántica nos puede ofrecer, ya que se trata de un campo cuyas posibilidades en el ámbito de la computación están casi tan sobredimensionadas como las de Guti en el ámbito del mediocampo del Real Madrid. Para ponernos en situación, es necesario empezar por algunos preliminares que nos ayuden entender el nicho en el que los computadores cuánticos pueden ser útiles.

En primer lugar, vamos a comenzar por definir un marco computacional (puede hacerse una discusión en términos más abstractos, pero es más simple centrar las cosas en un modelo concreto). Hay diferentes posibilidades, pero vamos a ser clásicos e inclinarnos por las máquinas de Turing (MT). Una MT es un modelo formal del concepto de algoritmo que podemos imaginar como un dispositivo capaz de leer/escribir símbolos de/en una cinta, y de desplazarse por la misma (o hacer que la cinta se desplace, que tanto da una cosa como la otra). La cinta la podemos imaginar como de longitud ilimitada, y dividida en casillas, en cada una de las cuales puede haber un símbolo. La MT se halla en todo momento en un cierto estado interno (de entre un cierto conjunto de estados posibles) y dispone de una función de transición interna que le dice qué debe escribir, cómo debe moverse, y cómo debe cambiar el estado interno en función del estado actual y de lo que esté leyendo en cada momento de la cinta. La definición de la MT es completa si indicamos el alfabeto A que contiene a todos los símbolos que se pueden leer/escribir, el conjunto de estados posibles Q, el estado inicial q₀, y la función de transición d. El funcionamiento de la MT termina en el momento que se alcanza un cierto estado de parada. Los contenidos iniciales de la cinta corresponden a la entrada del algoritmo, y los contenidos finales a su salida.

Esta definición de MT es suficiente para abarcar cualquier algoritmo (de hecho un algoritmo se define como una MT). En particular, un algoritmo cuántico es simulable en una MT, por lo que un supuesto ordenador cuántico no nos va a permitir nada que no podamos hacer con nuestro PC, Mac, o -ya puestos- ZX-81. Por supuesto, es posible que -aunque no pueda hacer nada nuevo- un algoritmo cuántico sí pueda ser más eficiente que un algoritmo clásico. Nos adentramos entonces en los vericuetos de la complejidad computacional, y necesitamos definir algunos conceptos adicionales, empezando por el de MT no determinista (nMT).

Una nMT es una MT en la que la función de transición puede estar sobre- o sub-especificada, es decir, se puede indicar más de un comportamiento en una determinada situación o ninguno en absoluto. Lógicamente, lo primero es más interesante. Podemos imaginarnos que cuando se produce una de estas situaciones en la que la función de transición indica más de una posibilidad, la nMT se ramifica, produciendo copias de la máquina que exploran estas posibilidades en paralelo. Contrariamente a lo que una primera impresión pudiera hacer pensar, este paralelismo masivo no nos permite nuevamente hacer nada que no pueda hacer una MT determinista, pero sí que permite realizar una tarea mucho más deprisa (exponencialmente más rápido). Podemos emplear esta posibilidad para realizar una clasificación de los problemas computacionales de decisión (problemas para los que tenemos que encontrar una respuesta SÍ o NO) en dos clases: P y NP. La primera comprende aquellos problemas para los que una MT determinista puede encontrar la respuesta en un número polinomial (en el tamaño del problema) de pasos, es decir, en algo del orden de n^c, donde n es dicho tamaño y c es una constante que no depende de n. Análogamente, NP es el conjunto de problemas de decisión para los que una nMT puede encontrar la respuesta en un número polinomial de pasos (es decir, basta con que una de las ramas encuentre la solución en tiempo polinomial). Hay numerosos problemas prácticos de optimización cuya versión decisional (e.g., la que tiene por respuesta SÍ o NO) está en la clase NP. Por ejemplo, el problema del viajante de comercio (TSP): dado un conjunto de ciudades, encontrar una ruta de longitud mínima que pase por todas las ciudades, sin repetir ninguna, y vuelva a la ciudad de partida. La versión decisional de este problema sería plantear: ¿existe un camino de las características requeridas cuya longitud sea inferior a K?

En relación al ejemplo anterior, no consta que el TSP (entre otros muchos problemas) esté en P, lo que hace plantearse la cuestión de si es que no se conoce aún un algoritmo polinomial para él, o es que realmente el problema es intrínsecamente no-polinomial. En otras palabras, dado que P está claramente contenida en NP (porque toda MT determinista es una nMT también), se ignora si la inclusión es estricta o no, esto es, si hay problemas en NP que no estén en P. Se cree que sí los hay, pero no hay demostración en un sentido o en otro (hay un premio de 1,000,000$ para quien lo consiga demostrar). Lo que sí se sabe es que o bien P = NP (en cuyo caso la necesidad de computadores cuánticos pasa a ser muy cuestionable), o bien hay tres tipos de problemas en NP: los problemas en P, y otros dos tipos que veremos a continuación, una vez se defina el concepto de completitud para una clase.

Se dice que un problema X es completo para la clase C, si X es un problema que pertenece a la clase C, y cualquier otro problema en C es reducible a X. A grandes rasgos, esto último quiere decir que dada una instancia de un problema Y perteneciente a C, podemos usar un cierto procedimiento R para convertirlo en una instancia del problema X. Si esto es así, X representa el mayor grado de dificultad dentro de la clase (cualquier otro problema es a lo sumo tan complejo de resolver como X). En el caso particular de NP requerimos que la transformación anterior se haga con un algoritmo polinomial. El problema de la satisfacibilidad es un problema completo para NP. Hay otros muchos que pueden consultarse aquí.

Bajo la suposición de que P no es igual a NP, los problemas NP-completos están lógicamente fuera de P, pero también hay problemas que ni están en P, ni son NP-completos. No consta que un algoritmo cuántico, gracias a la aceleración que el uso de estados superpuestos permita, pueda resolver en tiempo polinomial un problema NP-completo, y de hecho se piensa que no podrá. La utilidad de los computadores cuánticos será entonces para problemas no NP-completos como la factorización de enteros (una utilidad mucho más reducida de lo que los optimistas de D-Wave afirman). En otro artículo ya trataremos esto con más detalle, y lo cuantificaremos más formalmente. Vamos a esperar mientras tanto a ver en qué queda la presentación de Orión.