¿Qué es eso de que “P ≠ NP”?

El post de hoy es una colaboración junto con Héctor (a.k.a. Hekanibru) ya que estamos iniciando un nuevo proyecto juntos. Se trata de un nuevo blog, Pedazos de Carbono, en donde ambos vamos a estar publicando durante toda la semana notas de ciencia, filosofía y más. Si les late la idea no duden en ir al nuevo blog y subscribirse o, si lo prefieren, nos pueden seguir en Facebook.

Homero 3D en Los Simpsons

Si tienen amigos que estudian o trabajan en el área de computación, probablemente la semana pasada se encontraron con algunas noticias comentando que si “P”, que si “NP”, o que si más bien la verdad “N.P.I.” ¿De qué se trata eso? ¿De qué estaban hablando? ¿Y a qué vino tanto alboroto?

El alboroto vino porque Vinay Deolalikar—un investigador de HP labs—publicó un manuscrito (¡de más de 100 páginas!) en donde clama haber resuelto uno de los problemas abiertos, seguramente el más conocido y más importante de todos, en el área de computación teórica. Él dice tener una prueba de que “P ≠ NP” y, si su demostración es correcta, además de quedar inmortalizado en la historia de la computación recibirá también un millón de gracias dólares por parte del Clay Mathematics Institute como premio por haber resuelto uno de los Problemas del Milenio.

Desde el principio se observó que el trabajo de Deolalikar es un intento serio de resolver este problema y que, en efecto, descubre una serie de conexiones súper interesantes entre áreas tan diversas como la física estadística, lógica proposicional, probabilidad, y teoría de cómputo. Sin embargo, para su infortunio, las últimas noticias parecen indicar que su demostración tiene varios errores más o menos graves y no funciona al menos sin hacerle algunas fuertes correcciones o añadiendo nuevas ideas.

Pues qué mala onda, pero ¿de qué se trataba el problema o qué onda? Ha de estar bien fumado, ¿no?

Pues puede parecer medio fumado o abstracto, pero la verdad es que la pregunta que Deolalikar trataba de responder—y muchos otros investigadores antes que él—tampoco es que sea una cosa así super marciana que sólo cerebros superdotados puedan entender. La pregunta, de hecho, es relativamente sencilla.

Los teóricos de la computación clasifican los problemas que tratan de resolver según qué tan “complejos” son. P y NP son precisamente dos de estas clases en las que agrupan problemas, y se sospecha que los problemas que pertenecen a P son relativamente más “fáciles” que los que pertenecen a NP. Pero vamos a ver, ¿qué significa todo esto?

Sudoku en Wikipedia

¿Conoces el Sudoku? Seguro has visto esos jueguitos; traen una cuadrícula en la que están escritos algunos números y tu tarea es llenar los cuadritos vacíos siguiendo algunas reglas (por ejemplo que no se repitan números en un mismo renglón, etc.). Si has tratado de resolver uno, sabes que tienen su chiste, quizá a veces tienes que “adivinar” algunos de los números y—si te das cuenta que cometiste un error—regresar, borrar los números que están mal, e intentar de nuevo.

Pero ahora imagina que te doy un Sudoku ya con todos los cuadritos llenos y lo único que te pido es que verifiques si, según las reglas del juego, mi solución es correcta. ¡Eso es mucho más fácil! Lo único que tienes que hacer es, por ejemplo, ir renglón por renglón verificando que no hayan números repetidos y así comprobar que todas las reglas se cumplan. Ahora, ¿has visto esos mega-Sudokus? Si consideramos Sudokus más y más grandes, seguro te vas a tardar más y más tiempo en verificar si mi solución es correcta. Pero aquí la clave está en que el tiempo que te vas a tardar en verificar la solución tiene una relación muy particular y directa con el tamaño del Sudoku que yo te dé. Los computólogos, de hecho, dicen que el problema de verificar soluciones del Sudoku está en la clase P, ya que el tiempo que te tardarías en realizar esa tarea se puede expresar como un Polinomio que depende del tamaño del Sudoku en cuestión.¹

Por otra parte, el problema de resolver un Sudoku—el original donde tú tienes que tienes que llenar los cuadritos—es un problema que está en NP. Aquí NP significa “No determinista Polinomial” y es una manera rebuscada que los teóricos tienen de decir: “se vale que intentes todas las posibles soluciones una tras otra, por ensayo y error, siempre que verificar si una solución es correcta sea un problema en P”. Esto de hecho te sugiere un método, aunque un poco “bruto”, para resolver los Sudokus: intenta una tras otra toda las posibles soluciones y luego verifícalas hasta que te encuentres la correcta. Sin embargo, el tiempo que te vas a tardar siguiendo este método se “dispara” de manera exponencial respecto al tamaño del Sudoku. Pero si recuerdas tus clases de álgebra, ¡las funciones exponenciales no son polinomios! Esto parece sugerir que los problemas en NP son, de algún modo, más difíciles que los de P.

Pero justo esa es la pregunta del millón (¡literalmente millón de dólares!), ¿será que los problemas en NP son en efecto más difíciles que los que están en P? Dicho de otro modo, ¿es cierto que buscar soluciones a un problema es realmente más difícil que verificar soluciones de ese mismo problema? Y puede parecer increíble, pero este problema sigue abierto desde hace casi 40 años cuando a Stephen Cook se le ocurrió por primera vez.

La intuición parece decir que, ¡claro! buscar soluciones es más difícil que simplemente verificarlas. Sin embargo, aun con todo el conocimiento de cómputo que tenemos hasta ahora, no hemos podido descartar la posibilidad de que algún día a un programador brillante se le ocurra un método súper original que pueda resolver problemas como el de Sudoku en un tiempo polinomial.

Sin embargo lo que la mayoría de los computólogos piensan, y es lo que Deolalikar pensó que había demostrado, es que las clases de “P” y “NP” son diferentes. Es decir, hay problemas para los que buscar soluciones (no importa cuántos programadores brillantes tengas) siempre va a ser más difícil que verificarlas.

¿Ves? Al final toda esta cuestión “fumada” se pudo explicar con Sudokus. Ahora sólo resta ver qué va a suceder con la dichosa “prueba” de Deolalikar. ¡Hagan changuitos!

Hekanibru y Juan.

¹ Para ilustrar qué significa esto, imagina que dado un Sudoku lleno de n×n (ó n²) cuadritos, tú te tardarías, digamos, unos 3n² minutos en verficarlo. Dado que pudimos expresar la formulita del tiempo como un polinomio (3n²) que depende del tamaño del Sudoku (n²), ¡tenemos un problema en P!

Directo desde Pedazos de Carbono.

Social Juan

Estoy en San Jose, California, justo después de terminar la conferencia ICWSM sobre blogs y medios sociales. La primera noticia, y que ya muchos se enteraron en mis feeds de Facebook y Twitter, es que nuestro trabajo sobre el contenido compartido por bloggers en la red ganó el premio al mejor paper del workshop sobre datos!

A parte de, por supuesto, estar muy contento por el reconocimiento, tuve al fin la oportunidad de llevar a cabo uno de mis principales retos personales: Presentar la foto de un lolcat en un foro serio de investigación.


La investigación puede ser divertida. :-D

Ya hablando más en serio, la experiencia de asistir a este congreso fue sensacional. Aprendí muchas cosas nuevas e interesantes, de las cuales les voy a platicar en el resto del post. Es increíble la oportunidad que hoy en día el internet y las redes sociales nos dan para entender más de nosotros mismos, de la forma de relacionarnos con otras personas, y en general de nuestra forma de percibir al mundo.

Uno de los experimentos que más me gusto, realizado por Duncan Watts de la Universidad de Columbia, estaba diseñado para determinar que tanto la popularidad de una idea u objeto, digamos por ejemplo una canción, está determinada por propiedades particulares de la canción misma, o por un efecto social externo donde las canciones se vuelven populares simplemente porque hay mucha gente hablando de ellas, ocasionando que se vuelvan aún más populares, y que aún más gente hable de ellas, y así en una avalancha de creciente popularidad consecuencia de una cascada social.

Para probar esta teoría, Watts y su equipo de trabajo diseñaron una página Music Lab donde invitaban a jóvenes a descubrir música de nuevos artistas (todos ellos desconocidos) y bajar la música que les gustara.

Y aquí está la genialidad del experimento: Los usuarios que entraban a la página eran asignados, sin que ellos lo supieran y de manera aleatoria, a uno de 9 ‘mundos’. En uno de los mundos, los usuarios podían ver las canciones, escucharlas y bajar las que les gustaran. En los 8 mundos restantes a los usuarios se les mostraba además, junto a los datos de la canción, cuantas otras personas (dentro su mismo ‘mundo’) habían bajado ya la canción.

Los resultados fueron simplemente sorprendentes. Dentro del mundo donde los usuarios no podían ver cuantas personas habían bajado ya las canciones, la populariad de entre todas las canciones se distribuía más o menos de forma lineal, desde las menos a las más populares. En todos los 8 mundos restantes, sin embargo, la popularidad crecía de manera exponencial siguiendo esta regla de que “las populares se vuelven más populares”.

Más interesante aún, los ‘hits’ en diferentes mundos eran diferentes. Aún conociendo con exactitud toda la información sobre la popularidad de canciones en uno de los mundos, es muy difícil predecir cuales serán las canciones populares en otro de los mundos. Watts define, de hecho, una métrica de ‘impredecibilidad’ y demuestra que la influencia social incrementa esta métrica.

Otro tema recurrente, que aparecía una y otra ves en diferentes estudios, es el principio de ‘homophily’ que en simples palabras dice: “A las personas les gusta llevarse con personas que son y que piensan como ellas mismas”. Personas con gustos e intereses similares van a tender a reconocerse y seleccionarse como amigos.¹ En Facebook, por ejemplo, encontraron que el mejor predictor para ver si una persona va a subir fotos es si sus amigos han subido fotos.²

Varios de los estudios fueron realizados utilizando crowdsourcing donde se utiliza a grupos de humanos para resolver tareas que son fáciles de resolver para ellos pero difíciles para las computadoras. Esta idea la utiliza Google para etiquetar imágenes, y también fue así como Facebook tradujo su interfaz a diferentes idiomas. Para los que no quieren trabajar de gratis, Amazon tiene un sitio, Mechanical Turk, donde le pagan a humanos para realizar este tipo de tareas: “Inteligencia Artificial Artificial”.

Como puntada curiosa, uno de los investigadores se quejó de que uno de sus estudios en Mechanical Turk fue atacado por ‘bots’ haciéndose pasar por humanos resolviendo las tareas.³

Otro de los hechos que me llamaron mucho la atención fue que una buena parte de la discusión y registro de notas sobre puntos interesantes de la conferencia fue llevada a cabo, precisamente, en medios sociales. Mia, por ejemplo, publicó en su blog una serie de notas sobre la conferencia. Y más interesante aún fue el seguimiento e intercambio de opiniones ‘en tiempo real’ usando la hashtag #icwsm en Twitter.

Ya para terminar, les comento la última curiosidad y es sobre las hashtags que se usan en Twitter para agrupar información o comentarios respecto a un tema específico. Lo realmente curioso del caso es que las hashtags no fueron inventadas por Twitter, sino por los usuarios de Twitter. Casi como una ‘conciencia global’ se pusieron todos de acuerdo en adoptar esta convención que, aprovechando la función normal de búsqueda en Twitter, sirve precisamente para etiquetar comentarios que tienen un tema en común.

1. Dominique Cardon, et al. Does showing off help to make friends? Experimenting a sociological game on self-exhibition and social networks.
2. Cameron Marlow, Facebook. (Panel discussion)
3. Andrew Gordon, Identifying Personal Stories in Millions of Weblog Entries.

Redes Sociales

El martes pasado tuve la oportunidad de asistir a un workshop sobre investigación en redes sociales. Si, redes sociales, como Facebook, YouTube y Flickr. Y si, investigación, como la que se hace en universidades, centros e institutos de, uhm, investigación. Hasta hace poco más de un año no me había siquiera pasado por la mente que se pudiera hacer investigación en esta área. Después de pensarlo un poco, y de ir conociendo un poco más sobre el tema, me parece increíble la gran cantidad de problemas de investigación que se encuentran aquí: seguridad, privacidad, sistemas, redes, almacenamiento y distribución de datos, diseminación y popularidad de contenido, interfaces humano-computadora, minería de datos, sociología, psicología, y un gran pero gran etc.

En el MPI-SWS, donde trabajo, hay de hecho un grupo fuerte de investigadores trabajando en esta área. Y de estar atendiendo yo a sus pláticas y presentaciones, aunado al hecho de que la mitad de mi vida la pierdo de por si en redes sociales, fue que me fui interesando cada vez más en la investigación que hacen. Ya tuve incluso mi primer ‘pinino’ en el área: un trabajo sencillo pero interesante—que vamos a presentar en Mayo—en el contexto de blogs y sobre cómo videos de YouTube se esparcen por la “red de blogs”. Pero bueno, el recuento detallado del artículo y de los resultados que encontramos los prometo para otro post en unos días más. (Ya lo quiero escribir, pero mi co-autora sigue haciendo cambios y correcciones “de estilo” al artículo, y me quiero esperar a tener la versión definitiva.)

Este post es, por lo pronto, sobre algunas de mis experiencias en el workshop y, en particular, uno que me pareció el mejor de los trabajos presentados. El trabajo lleva el título de “Eight friends are enough” (Ocho amigos son suficientes) de Joseph Bonneau, Jonathan Anderson, Ross Anderson, y Frank Stajano de la Universidad de Cambridge [1]. Veamos de que se trata. Quizá algunos de ustedes han notado que, si buscas el nombre de alguna persona en Google, es probable que te encuentres con alguna información sobre su perfil en Facebook.


Esto es posible ya que Facebook, por default, publica una versión ‘pública’ de tu perfil. El perfil incluye datos básicos sobre ti: tu nombre, la foto de tu perfil, la región a que perteneces, algunas de tus páginas favoritas, y una selección al azar de 8 de tus amigos. La idea de estos perfiles públicos es que tus amigos o familiares te puedan encontrar buscando tu nombre en Google, y la lista de 8 amigos es para ayudar a darles una idea sobre si la persona que encontraron eres tú, o quizá es alguien más que tiene un nombre parecido.

El que si los perfiles públicos son o no una buena idea, es definitivamente un punto interesante, pero que no discutiré en este post. Lo único que voy a comentar es que: (1) yo si tengo perfil público y (2) si no te gusta la idea, puedes eliminar este perfil en las opciones de Facebook.

Regresando a lo interesante en este momento, que es sobre el artículo presentado en el workshop, es que los investigadores de Cambridge se preguntaron: “¿Será posible obtener, a partir de los 8 amigos que se muestran en el perfil público, alguna información sobre la estructura real de la red de amigos en Facebook?”

En primera instancia parece que no puedas extraer mucha información sobre mi si te digo quienes son 8 de mis 227 amigos en Facebook. Sin embargo, hay un punto interesante a notar: es probable que en algunos de los perfiles públicos de mis 227 amigos, aparezca yo listado como uno de sus amigos. Esto no te va a servir para obtener la lista completa de mis amigos (ni en general tampoco para obtener la red completa de amigos en Facebook) pero si parece estar dando algo más de información de la que aparentaba en un principio.

Por supuesto, el problema es aún más interesante cuando se plantea de forma general y en términos un poco más matemáticos: “¿Qué tanta información se puede extraer sobre un grafo (una colección de nodos y aristas) cuando sólo tienes acceso a k vecinos (determinados al azar) de cada nodo?”

Los autores encontraron que (usando diversos trucos y algoritmos de grafos) es posible aproximar con buena exactitud, propiedades interesantes del grafo como: número de vecinos (amigos), centralidad de los nodos, conjuntos dominantes (conjunto pequeño de nodos cuyos vecinos cubren toda la red), rutas cortas entre nodos, y comunidades en la red.

Sobre el porqué estas preguntas “matemáticas” son interesantes en el “mundo real” considera lo siguiente: Alguien malicioso podría tratar de comprometer las cuentas (robar sus passwords) de los usuarios en un conjunto dominante de la red, y usarlas para difundir spam entre la mayor cantidad de usuarios en Facebook y con el menor esfuerzo posible. Nodos centrales, por otra parte, pueden ser utilizados para interceptar, con alta probabilidad, la mayoría de los mensajes que recorren la red.

Muy interesante fue que los investigadores asistentes al workshop inmediatamente comenzaron a proponer, discutir y debatir diferentes ideas sobre cómo modificar los perfiles públicos de Facebook para poder seguir mostrando 8 amigos pero sin exponer, al mismo tiempo, tanta información sobre la red de amigos. ¿Elegir amigos al azar, pero con preferencia a ‘ciertos’ tipos de amigos? ¿Incluir algunos amigos ‘falsos’? ¿Incluir una mezcla de amigos directos, y amigos de amigos? ¿Limitar el número de perfiles en los que una persona aparece como “amigo de”? Algunas de estas ideas parecen funcionar, en el sentido de que los métodos de Bonneau, et al ya no serían aplicables, o darían resultados imprecisos, pero pueden traer otros problemas prácticos (¡yo no quiero amigos falsos en mi perfil!) o técnicos (difíciles o costosos de implementar). De cualquier modo, esto dará definitivamente para algo más de investigación muy interesante al respecto. I love research.

Como otra nota curiosa, y ya para ir terminando este post, les comento que me tocó compartir habitación con uno de los empleados de Facebook que trabaja en el equipo de seguridad (previniendo y reaccionando cuando hay ataques de spam o cuentas robadas). Respecto a los cambios recientes en el “Nuevo Facebook” comentó que tuvieron, de hecho, una activa discusión dentro de la empresa sobre los cambios que implementar. No tanto sobre el diseño o “las esquinas redondas” en las fotos, que tristemente parece ser lo único que los “quejosos del Nuevo Facebook” parecen notar, sino sobre la funcionalidad de un componente importante: la News Feed.

Una fracción de los empleados proponían mantener y mejorar una feed “inteligente” que te muestra más noticias sobre los amigos con los que más interactúas, y con controles para “ajustar” los tipos de noticias que prefieres recibir y de cuales de tus amigos (e.g. un poco más de este amigo, un poco menos de este otro). La otra fracción, argumentando que los usuarios de Facebook son “tontos” y no entienden (ni les interesan) estas listas inteligentes, proponían una feed “tonta” que simplemente mostrara, en tiempo real, todas las noticias, de todos tus amigos, con filtros “simples” por grupos de amigos o por tipos de noticias. ¿Adivinen quienes ganaron la discusión? Si, la feed que tenemos ahora muestra las noticias en tiempo real.

Etiquetando Fotos

Este es un post que quise escribir hace muucho tiempo, recién que Picasa agregó esta opción, de mis experiencias etiquetando las fotos con los nombres de las personas que aparecen en ellas. Como siempre, nunca tuve tiempo, pasaron los meses y luego como que ya no venía al caso la ‘noticia’.

Resulta que, por otra parte, hace algunas semanas me puse a organizar mis contactos en Gmail, ya que ahora se sincronizan directo con mi celular! El único problema fue que, como efecto no deseado de la movedera de contactos, le di en la torre a las etiquetas en Picasa que usa también los contactos de Gmail para asignarles identidad a las caras en las fotos.

Me encanta la dirección a la que nos están llevando estas nuevas tecnologías, tener la ilusión de un único banco ‘centralizado’ con todos nuestros datos en la nube, y accesibles desde cualquier aplicación o dispositivo. El único problema es que en el camino, y mientras nos ponemos de acuerdo en los estándares para compartir datos entre aplicaciones (y no XML no es la respuesta) hay que sufrir de ves en cuando con estos efectos secundarios no deseados.

Pero bueno, al grano con el etiquetado de las fotos. Muchos estarán ya acostumbrados a los tags en fotos, que fueron popularizados primero por Facebook, para identificar a las personas que aparecen en ellas. Esto, aunque de entrada pareciera un detalle o una simpleza, abre un sin fin de oportunidades y posibilidades para la computadora que ahora tiene más conocimiento semántico de las fotos. Ahora te puedes enterar fácilmente, por ejemplo, de cuando alguien sube fotos en las que tu o tus amigos aparecen. Puedes buscar también fotos en las que sales tu con x o y persona.

Y bueno, todo genial excepto por el pequeño problema de que nosotros, como humanos, tenemos que estar haciendo el trabajo de manualmente ir seleccionando y etiquetando a las personas en cada fotografía. El paso siguiente en la evolución de esta tecnología es, obviamente, hacer que este proceso sea lo más automático posible. Y esto es lo que el algoritmo de reconocimiento de caras de Picasa comienza a hacer.

Picasa detecta automáticamente las caras en las fotos, y las agrupa según las que parezcan ser la misma persona. Además, después de comenzar a etiquetar las primeras fotografías, el sistema va aprendiendo, y sugiriéndote cada vez con mejor precisión quienes son las personas que aparece en cada fotografía. Aunque no totalmente automático, el sistema ayuda bastante a etiquetar rápidamente todas tus fotografías. En mi colección de fotos, por ejemplo, Picasa detectó poco más de 2500 caras, y las pude etiquetar todas hoy en unas 4 horas. No del todo ideal, pero definitivamente mucho más rápido que estarlo haciendo manualmente como en Facebook.

La tecnología está definitivamente aún en pañales. El algoritmo a veces falla y detecta a rocas u otros objetos como ‘caras’. Me pareció incluso simpático que uno de los errores comunes era cuando, hmm, los pechos de las mujeres eran equivocadamente detectados como caras. :-P


Pero bueno, aún con todos sus problemas actuales, la tecnología está avanzando a pasos agigantados. No la he podido probar aún (me muero de las ganas), pero el nuevo iPhoto '09 tiene implementada ya también una opción similar. No me extrañaría para nada que, en unos cuantos años, las cámaras mismas hagan ya el proceso de etiquetado, de modo que incluso instantes antes de tomar la fotografía, la cámara sepa ya quienes son las personas que aparecen en ella.

Lo que hace unos años parecía increíble, hoy nos parece ya cotidiano.

Hypergame Paradox

I've recently hear about this paradox which I didn't knew before. It surprised me, because I'm a fan of paradoxes, and this one is quite neat. I also wanted to post about it, because when I tried to google for it, the first few hits weren't really relevant, or seemed to have an incorrect explanation of the paradox.

So, this paradox is about games. In particular, we are interested in 2-player games which are played in turns. We say that one of such games is a finite game if, no matter what the players do, the game eventually ends after a finite number of turns. For example, Chess is not a finite game since, after playing for a while, the players might decide to pick one of their pieces, say a rook, and forever move it back and forth between two squares on the board. On the other hand Tic-Tac-Toe is a finite game, since it can only take at most 9 turns, when the board will be full and the game will end either in a tie, or with one of the two players winning.

Now, hypergame, is a really fun game whose rules are as follows: the first player starts by choosing a finite game to play; then the second player has the first turn in the game selected, and then they keep playing that game as usual. Whoever wins the game selected by the first player, is also the winner of hypergame.

It turns out, interestingly, that hypergame is also a finite game! Observe that, no matter which game the first player chooses to play, we know that the selected game is a finite game, and must also terminate after a finite number of turns.

However... if hypergame is a finite game, the first player then might also decide “let's play hypergame” as his first move. The second player, which has to start now playing hypergame, might choose as well “let's play hypergame!”, ... and so on, forever, ...

So, we are left with the paradoxical question, is hypergame a finite game or not?

The first programmer

Ada Lovelace is mainly known for having written a description of Charles Babbage's early mechanical general-purpose computer, the analytical engine. She is today appreciated as the "first programmer" since she was writing programs—that is, manipulating symbols according to rules—for a machine that Babbage had not yet built. She also foresaw the capability of computers to go beyond mere calculating or number-crunching while others, including Babbage himself, focused only on these capabilities.

Curiosidad cortesía de AR.

— Jesus...
— What?
— I just thought... you were a guy.
— Most guys do.

The Matrix

I need a real job

RoboCup 2007

Ha comenzado este año en Atlanta uno de los eventos más divertidos e interesantes en el mundo de la robótica: RoboCup 2007.

RoboCup es una serie de concursos organizados con el fin de motivar la investigación en robótica e inteligencia artificial, tratando de desarrollar robots que sean capaces de jugar fútbol. La meta es, según los organizadores del evento, crear para el año 2050 un equipo de robots autónomos y humanoides que pueda vencer al equipo humano que sea campeón del mundo en fútbol.

Un estudiante de la universidad de Georgia Tech mantiene en su blog una colección interesante de fotos y videos del evento, de donde tomé prestado el siguiente. Enjoy!

Googleando y programando

El escenario: Más de alguna vez cuando estoy programando, necesito buscar la documentación de alguna función o librería y, quién lo pensaría de mi, suelo abrir un navegador para buscar en Google la información que necesito.

El problema: Seguro a muchos les ha pasado también que, en este contexto, la búsqueda de Google no es siempre muy efectiva. La red esta minada con sitios de poca calidad que suelen atraer visitantes diluyendo un poco de información “relevante” en medio de un mar de anuncios. Éste es por ejemplo el primer resultado hoy al buscar c++ vector, créanme que hay mejores referencias. Y seguro que tampoco les cuesta trabajo imaginar el tipo de cosas que puedes encontrar cuando, ingenuamente, tratas de buscar algo como LaTeX blog.

La solución: Google Co-op lanzó hace algunos días Custom Search Engine. La idea básicamente es crear buscadores para temas específicos sesgando los resultados mediante keywords y etiquetas. Para los interesados en inteligencia artificial y lógica denle también una checada a la teoría detrás del proyecto pues se acerca a la dichosa Semantic Web sólo que etiquetando al nivel de sitios (y no páginas individuales o el contenido de las mismas).

Yo comencé ya a crear un buscador orientado a lenguajes de programación en general y lo pueden probar aquí. Aunque no he podido dedicarle mucho tiempo para configurarlo (por lo pronto solo he agregado y etiquetado 8 sitios) ya se puede ver un adelanto interesante al buscar cosas como vector. Observa que además, gracias al etiquetado, puedes ahora refinar la búsqueda por lenguaje de programación.

La otra parte genial de este proyecto es que es cooperativo así que les pido de favor a todos programadores interesados que se encuentren con este post, que vayan a la página del buscador y que se apunten para contribuir agregando algunos otros sitios que conozcan con información relevante. ¡Creo que esto puede ser muy útil para todos!

Ah, por cierto, esta no es sólo una herramienta para los programadores. Todos pueden jugar y experimentar con el Google Custom Search y crear buscadores para cualquier tipo de temas como deportes, películas, ciencias, salud, entretenimiento, etc. En verdad cualquier tema que te interese.

Give it a try!

De paradojas y cosas no computables

Recientemente me encontré con el trabajo de un grupo de científicos que descubrieron algunas relaciones entre la compresión de texto (generar archivos comprimidos como los .zip), la interpretación de lenguaje natural (que las máquinas hablen y entiendan nuestro lenguaje) y problemas de inteligencia artificial en general.

La primera vez que escuché esto me pareció un completo disparate pero, después de estarlo leyendo con un poco más de calma, he visto que la idea es realmente muy interesante y parece tener bastante sentido. Incluso, además de tener unos tintes medio filosóficos geniales, todo está fundamentado en resultados matemáticos formales. También me he dado cuenta de que las ideas, aunque no son nada triviales, tampoco parecen imposibles de entender para nosotros los simples mortales.

Éste es entonces el primero de una serie de posts donde trataré de ir explicando varios de los componentes involucrados en esta teoría. El tema de este post es la llamada complejidad de Kolmogorov que, si no dejamos que nos espante mucho el nombre y leyendo con un poquito de atención, veremos que finalmente no es algo tan complejo como aparenta. ;-)

Empezamos con una simple cadena de texto. La dichosa complejidad es un numerito que trata de medir que tan ‘complicado’ es generar esa cadena con un programa en la computadora. Por ejemplo, la cadena de texto

  “hola hola hola hola hola hola hola hola ”

la podríamos escribir en la pantalla usando el siguiente programita

  repite 8 veces escribe "hola "

Algo interesante es que este programa se puede ver, además, como una cadena de texto

  “repite 8 veces escribe "hola "”

que, en este caso, está formada por 30 caracteres (contando todas las letras, símbolos y espacios). Observa como la cadena original, la de muchos hola’s, tenía 40 caracteres y la hemos podido generar con un programa que ocupa sólo 30.

Pero no todas las cadenas de texto son tan simples como repetir “hola” un montón de veces. Por ejemplo, para la cadena de 40 caracteres

  “u8agup2pPy3J087z4m9krF6c9gE00Uo6AOLox56m”

quizá el programa más corto que la escriba en pantalla es

  escribe "u8agup2pPy3J087z4m9krF6c9gE00Uo6AOLox56m"

que ocupa en total 50 caracteres.

Entonces, la complejidad de una cadena de texto, como la definió este señor Kolmogorov, es el tamaño (en no. de caracteres) del programa más pequeño que escriba dicha cadena en la pantalla.

En el último de los ejemplos vimos cómo, para cualquier cadena de texto, es muy fácil conseguir un programa que la escriba; basta con agregarle unos 10 caracteres extras: “escribe "..."”. Esto quiere decir que la complejidad de una cadena no puede ser mucho más grande que el tamaño de la cadena misma. En el peor de los casos el programa tendrá 10 caracteres extra pero, en muchos otros casos, es posible encontrar programas más pequeños.

Imagínate en mi primer ejemplo que la cadena dice “hola ” pero, en lugar de 8, unas 5000 veces. La cadena de texto tendría ahora unos 25000 caracteres, mientras que el programa para escribirla en pantalla sigue siendo pequeñito

  repite 5000 veces escribe "hola "

y ocupa, después de cambiar el “8” por “5000”, ¡tan sólo 33 caracteres! Observa como aquí comienzan a aparecer algunas relaciones con compresión, una cadena de 25000 caracteres la pudimos comprimir en una de 33.

Espero que hasta aquí vaya todo más o menos claro, porque vamos a comenzar ahora con cosas más divertidas. Y es que vamos a mostrar que calcular la complejidad de una cadena es una tarea, digamos, muy difícil.

Supongamos que un amigo muy inteligente nos ha hecho el favor de escribir un programita al que le damos una cadena de texto y nos regresa la complejidad de esa cadena. El programa se vería más o menos así:

  Complejidad(Cadena S) regresa Número
  inicio
    /* Un código súper inteligente va aquí */
  fin

Ya que tenemos este programa, vamos a escribir nosotros este otro

  EncuentraCadena(Número N) regresa Cadena
  inicio
    por cada Cadena S
      si Complejidad(S) > N entonces regresa S
  fin

¡No se espanten! Voy a explicar ahora de qué se trata todo esto. Nuestro nuevo programa recibe de entrada un número, N, y va a dar como salida una cadena de texto. La cadena que obtenemos en la salida tiene la única peculiaridad de que su complejidad es más grande que N, el número que le demos de entrada.

Y el funcionamiento de este programita tampoco es nada complicado. Lo único que hace es ir generando una por una todas las posibles cadenas de texto (esto es lo que indica el ‘por cada Cadena’) y llamando a la rutina Complejidad para ver si hemos encontrado o no una cadena con complejidad mayor a N. En cuanto encontremos la primera cadena con complejidad mayor a N el programa termina y regresa como resultado esa cadena.

Recapitulando, este es el código que llevamos escrito hasta ahora.

  Complejidad(Cadena S) regresa Número
  inicio
    /* Un código súper inteligente va aquí */
  fin

  EncuentraCadena(Número N) regresa Cadena
  inicio
    por cada Cadena S
      si Complejidad(S) > N entonces regresa S
  fin

Recordemos que la linea donde dice ‘Un código súper inteligente va aquí’, efectivamente, tenemos reemplazarla por el código que nos haya dado nuestro amigo. Ya que hayamos escrito ese código podemos entonces contar el total de caracteres que ahora ocupa todo el programa completo hasta este punto. Digamos que los contamos y resulta que en total hay unos 5000 caracteres.

Podemos agregar entonces el siguiente pedacito de código al final de nuestro programa.

  escribe EncuentraCadena(8000)

Veamos que es lo que hace este programa. En realidad es muy sencillo, simplemente busca una cadena que tenga complejidad mayor a 8000 y la escribe en pantalla.

¿Puedes ver algún problema? Veámoslo de nuevo. Hemos construido un programa que, en total, ocupa unos 5030 caracteres e imprime una cadena de complejidad mayor a 8000. ¿Recuerdas la definición de complejidad? Es el tamaño del programa más pequeño que escribe la cadena. Según el código súper inteligente de nuestro amigo, el programa más pequeño necesita unos 8000 caracteres, pero nosotros hemos logrado escribir esa cadena ¡con sólo 5030!

¿Qué significa todo esto? Pues lo primero es que nuestro amigo súper inteligente nos mintió y el código que nos dio para calcular la complejidad de una cadena no funciona. De hecho no funciona porque, no se puede escribir ningún programa para calcularla. Lo que hemos demostrado es que, no importa qué tan inteligente sea nuestro amigo, nunca podrá escribir el dichoso programita porque eso genera contradicciones. En otras palabras hemos probado que la complejidad de Kolmogorov no es computable.

¿Y, qué significa eso? En palabras más sencillas, una de las implicaciones de este resultado es que nunca podremos programar el compresor de archivos perfecto. Y ojo que eso no quiere decir que no podamos comprimir archivos, eso sí que lo podemos hacer y es lo que hacemos cuando generamos archivos .zip. Lo que no podemos tener es la garantía de haber podido comprimir los archivos lo más posible.

Ya para terminar sólo quiero mencionar que, para hacer la explicación más sencilla, tuve que sacrificar un poco la formalidad de la demostración. Pero espero que me puedan creer que esto se puede hacer formalmente sin ninguna ambigüedad, usando por ejemplo un lenguaje de programación real apropiado. En particular el ‘por cada Cadena’ se puede implementar fácilmente generando las cadenas en orden, primero las más chicas y luego las más grandes; y las del mismo tamaño ordenadas alfabéticamente.

También para los curiosos, o si alguien se perdió entre tanta explicación y cosa rara, una versión más informal del mismo argumento es la Paradoja de Berry.

Computación basada en humanos

Uno de mis nuevos héroes personales, Luis von Ahn, es uno de los precursores principales de una nueva idea que me parece extremadamente simple pero, al mismo tiempo, muy ingeniosa y quizá hasta revolucionaria.

La idea proviene de darnos cuenta que hay cierto tipo de problemas que, actualmente, los humanos podemos resolver mucho mejor que las computadoras. Uno de esos problemas es, por ejemplo, interpretar imágenes y reconocer objetos en ellas.



Para un humano es fácil ver que en esta foto hay una mujer, con una blusa azul. Hay también unas flores, parecen tulipanes. Una tasa, una computadora con monitor, teclado y mouse. La mujer esta sentada en una silla frente a un escritorio. Si miran también con cuidado, en el fondo hay una lámpara y un teléfono.

Mientras que, por otro lado, uno de los mejores programas que se han creado en visión por computadora tiene problemas tan sólo para reconocer que hay un rostro en esa imagen: Sorry, no faces were detected.

Y las aplicaciones potenciales de resolver un problema como éste son también evidentes: obtener resultados mucho más precisos y relevantes cuando hacemos una búsqueda de imágenes, proveer a personas con deficiencias visuales de una descripción detallada de imágenes en la red, conseguir más y mejores datos para entrenar algoritmos que realicen el reconocimiento automático de imágenes.

Bien ahora la pregunta es, ¿cómo reclutar a miles de humanos en todo el mundo que estén dispuestos a perder su tiempo etiquetando imágenes de la red? Podríamos pagarles para hacerlo pero, seguramente, eso terminaría siendo muy caro. “We need something that is cheap and fast”.

“¿Por qué no podríamos ...”, piensa von Ahn, “... hacer que las personas quieran desperdiciar su tiempo etiquetando imágenes? ¿Por qué no hacerlo... ¡divertido!?” Así es como surgió la idea del ESP Game.

Extrañamente adictivo, el juego te conecta con otro jugador en alguna otra parte del mundo, no puedes comunicarte con tu compañero y lo único que tienen en común es que están viendo la misma imagen. El reto es lograr escribir ambos una misma palabra que describa a la imagen. Cuando los dos logran coincidir en una palabra ambos ganan puntos, y se les muestra una nueva imagen. El objetivo del juego es ganar la mayor cantidad de puntos en una cantidad fija de tiempo. “Points make people happy”.

Si quieren enterarse un poco más de las ideas y la teoría detrás de este tipo de computación basada en humanos, les recomiendo enormemente ver el video de la plática que Luis von Ahn dio en Google al respecto. No es para nada técnica y, por el contrario, deja ver como el tipo es simple y sencillamente un genio.

Google acaba de lanzar, basado en esta misma tecnología, su etiquetador de imágenes. Y en principio, en manos de Google, esta idea corre el peligro de crecer desenfrenadamente de manera exponencial. Desafortunadamente el programa está aún en etapas demasiado beta. Al menos la última ves que lo jugué, el juego solía trabarse y las imágenes son a veces demasiado pequeñas. Espero que arreglen pronto estos problemas, porque la idea es genial y no hay más. Como sea, si están interesados y quieren jugar los exhorto de nuevo a desperdiciar sus human cycles en el fabuloso ESP Game.

La idea en Matrix de que las computadoras decidieron no eliminarnos a los humanos porque nos necesitaban como baterías es increiblemente ridícula. Pero que tal ésta: decidieron conservarnos para resolver por ellas problemas en los que los humanos somos mejores.

Ésto me recuerda también a una computadora llamada Earth que construyeron los ratones para calcular la última pregunta de la última respuesta sobre la vida, el universo y todo. :-S