La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Posts Tagged ‘VLSI’

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

Posted by Carlos en agosto 10, 2009

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

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.

Anuncios

Posted in Complejidad, Juegos, Optimización Combinatoria | Etiquetado: , , , , | 1 Comment »

Resuelve problemas NP-completos mientras juegas

Posted by Carlos en julio 29, 2009

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

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.

Posted in Complejidad, Juegos, Optimización Combinatoria | Etiquetado: , , , | 2 Comments »