¿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.

Inception

El viernes me lancé al cine a ver la película de Inception (según esto llamada “El Origen” en México). Para empezar y en pocas palabras voy a decir que la película me encantó, está muy original, entretenida y, si no la han ido a ver, definitivamente la recomiendo. Ojo que tampoco es la mega película del siglo. En especial si no la han visto, no vayan al cine con demasiadas expectativas. Sí, está buena, pero no es así para taaanto (si ustedes son como yo me lo van a agradecer).

Algo que me gusto bastante de la película es que da bastante de que hablar, para filosofar y para pensar un rato. Lo que sigue de este post son algunas de las reflexiones y mi crítica personal sobre la cinta. Obviamente esto contiene spoilers masivos que les van a arruinar totalmente la experiencia si no la han visto. Así que esta es su última advertencia, si no han visto la película, dejen de leer aquí, vayan a verla, y regresen luego de nuevo.

<!-- here be spoilers -- here be spoilers -- here be spoilers -->

Antes que nada, Inception es una película que te hace pensar, y en mi libro cualquier película que te hace pensar es una buena película. He escuchado la crítica de que, de hecho, la trama es en realidad muy simple, y estoy también de acuerdo que Christopher Nolan nos lleva despacito y de la mano para que nos vayamos a perder demasiado. Sobre esto tengo sentimientos encontrados, por un lado sí me hubiera gustado que la película fuera un poco más atrevida y complicada, pero por otro lado creo que justo esto es lo que está provocando tan buena recepción de la película entre la mayoría de la gente. Es una película interesante, que te reta a pensar, pero sólo lo suficiente para que no perderte y dejarte con una sensación de wtf? Esto en contraste con Memento, película también excelente, pero que no cualquier persona soportaba sin caer en algún punto en el fastidio.

Ahora, de entre los detalles que no me gustaron, lo más grande y obvio es que toda la ‘teoría’ de los sueños en Inception está mal. Es cierto que dentro de los sueños sucedían normalmente cosas más extrañas e ‘imposibles’, sin embargo aún así los sueños parecían seguir ciertas ‘leyes’, de alguna manera eran coherentes. En una palabra, los mundos de los sueños tenían física. Lo cual todos sabemos que no es así. Los sueños en la realidad (¡ja!) suelen ser normalmente incoherentes, las cosas cambian de un momento a otro sin necesidad de explicación, no son consistentes ni tienen ninguna física aparente. A mi gusto un tratado cinematográfico (una peli pues) que mejor representa lo que ocurre dentro los sueños es Eterno resplandor, ahí si mis respetos para Charlie Kaufman, es un genio.

Recuerdo la escena en Inception donde tratan de convencer a Fisher (el hijo del empresario japonés que se acaba de morir) de que está dentro de un sueño diciéndole algo como: “Mira, ¡la gravedad está toda mal!” Si a mi me dicen eso en mi sueño yo sólo diria, “¿Huh? ¿Que no es así esto siempre? ¡Mira, puedo volar! ¡Woooo! ¡Órale! ¿Qué hacen ahí esos dinosaurios?” Creo que pueden ver el punto.

Otro problema con la ‘teoría’ de los sueños de la película es que, según esto, los sueños dentro de los sueños están anidados unos dentro de otros y el tiempo dura más y más entre más profundo estés en estos niveles de sueños. Además, en cada nivel tienes que dormir y de nuevo ‘soñar’ para ir al siguiente nivel. No soy ningún experto en el tema pero, de mi propia experiencia con sueños lúcidos, creo que esto no es así. Los despertares falsos no se sienten como un sueño dentro de un sueño, el sueño sigue siendo una secuencia lineal de hechos, lo único que ocurre es que de pronto (como parte de la ‘trama’) sueñas que ‘despiertas’ (¡sin necesariamente haber soñado que te duermes!). Y la ‘percepción’ del tiempo no parece ser diferente en ninguno de estos diferentes ‘segmentos’ de sueños.

Pero bueno, esto es una película y Christopher Nolan decide que en la teoría de los sueños para su película los mundos tienen sí física y los sueños dentro de los sueños efectivamente están anidados unos dentro de otros. Pero una ves que suspendes tu incredulidad y aceptas su propuesta, la Teoría de Nolan está bien definida y se mantiene consistente a lo largo de la película. Además su teoría sirve para darle forma a la trama y es un pretexto genial para presentar algunas de las escenas más increíbles.

Por ejemplo el hecho de que la física en un sueño se vea afectada por lo que está ocurriendo con la persona durmiendo “un nivel arriba” es un pretexto perfecto para regalarnos toda la secuencia en que la camioneta se está volcando y eso ocasiona ingravidez en el hotel. La verdad es que yo amé todas esas escenas con falta de gravedad, visualmente eran simplemente espectaculares. (¡Y espero con ansias el DVD para ver cómo las filmaron! De lo que he leido por ahí no fueron gráficos por computadora.)

Por otra parte los sueños anidados y la dilatación del tiempo de un nivel al siguiente fueron también un buen pretexto para introducir de una forma muy gráfica el concepto del crecimiento exponencial. Al menos para mi esto funcionó muy bien en la película, agregando a la tensión de la trama podíamos ver como el trabajo realizado por el equipo de ‘inceptores’ en los niveles más bajos de los sueños tenían sus minutos contados por los segundos que tardaría en caer la camioneta al agua.

Y esto me da pie también a otra de las razones por las que me gustó mucho la película: que está levemente salpicada de demostraciones de varios conceptos y curiosidades matemáticas. Ya mencioné el caso del crecimiento exponencial, está también el reflejo infinito cuando se ponen dos espejos de frente y, la más obvia de todas, la escalera infinita de Penrose. Aunque respecto a esta última debo decir que no me gustó que hayan revelado el ‘truco’ para construir la escalera en la realidad, ¡no hacía falta!, están en un sueño, los objetos imposibles son posibles y no hay nada que impida la creación de una escalera infinita como esa. Más allá de ese detalle, me fascinó ver la demostración de la escalera con presupuesto y efectos especiales del nivel de Hollywood.

Antes de esta, la versión más popular de la escalera yo creo que es de M. C. Escher en Ascendiendo y Descendiendo. La influencia de Escher la encontramos también cuando Ariadne ‘dobla’ la física de la ciudad y, por un instante, podemos ver cómo un hueco en el piso en uno de los dobleces se convierte en un túnel para otro de ellos. Siendo honestos creo que la película podría haber hecho mucho más uso del arte de Escher, pero no me puedo quejar de la probadita que se nos dio.

Hablando de Ariadne, mi personaje favorito, la mitología griega estuvo también fenomenal. Según el mito griego Ariadne es quien ayuda a Theseus a salir del laberinto del Minotauro. En la película Ariadne es realmente quien dirige las acciones de Cobb (DiCaprio) para enfrentarse a Mel (símbolo de sus culpas y remordimientos en la figura de su esposa). Ariadne es quien, con la implantación de una idea, ayuda a Cobb a escapar por si mismo del laberinto en el que hasta entonces se había encontrado atrapado.

Y a ustedes, ¿qué les pareció la película?

Double positive

Actually, languages can be very tricky in this respect. The eminent linguistic philosopher J. L. Austin of Oxford once gave a lecture in which he asserted that there are many languages in which a double negative makes a positive, but none in which a double positive makes a negative — to which the Columbia philosopher Sidney Morgenbesser, sitting in the audience, sarcastically replied, “Yeah, yeah.”

A note by Steven Strogatz on The Enemy of My Enemy

Prometo pronto dejar de estar poniendo puras quotes (hint: preparando nuevo artículo secreto interesante), pero está me pareció muy divertida. Por cierto, la cita viene de una serie de artículos por Steven Strogatz en el New York Times explicando matemáticas (desde contar hasta ¡geometría diferencial!) en un lenguaje muy sencillo pero, sobre todo, haciéndolo interesante, divertido y fácil de entender. El primer artículo de la serie es From Fish to Infinity, y el resto los pueden encontrar en su lista de colaboraciones. Los que le hacen a eso de las feeds, se pueden suscribir aquí para recibir nuevos artículos.

Gracias a Pablo por el tip.

Ágora

Dirigida por el chileno Alejandro Amenábar—quien estuvo también detrás de Tesis, Abre los ojos, Los otros, y Mar adentro—pronto estará en los cines su nueva cinta: Ágora.

¿Qué tendrá de especial esta película? Una palabra: Hipatia.

Para quienes eso sea suficiente, dejen de leer aquí y mejor vayan a ver el trailer.

Para los que siguen aquí conmigo: Hipatia es una mujer que ocupa un destacado lugar en la historia de la humanidad. Ella vivió en Alejandría, parte del imperio romano en la época en que el cristianismo se estaba convirtiendo en una fuerza principal, y la antigua religión politeísta egipcia iba de salida al final del período helenístico.

Hipatia era una científica, antes de que existiera la ciencia moderna, y es reconocida como la primera matemática notable de la historia. También una gran filósofa y astrónoma, cuenta entre su trabajo la edición y comentario de importantes obras como la Arithmetica de Diofanto, los Elementos de Euclides, así como libros propios en geometría, álgebra y astronomía. Ella propuso también un diseño del astrolabio, un instrumento utilizado para determinar la posición de las estrellas en el cielo, e inventó un hidrómetro, utilizado para medir la fuerza del caudal de agua por ejemplo en un río.

Murió trágicamente, linchada por una turba de cristianos en un marco de hostilidades y luchas políticas entre distintas facciones de la iglesia, el patriarcado de Alejandría, y el poder imperial romano.

La verdad es que todas las películas anteriores de Amenábar me han encantado, lo que me da confianza y me hace pensar que la historia de Hipatia está en buenas manos. En España la película está anunciada para Octubre, así que estén pendientes cuando aparezca también en los cines donde quiera que se encuentren. Ah, y por supuesto, no dejen también de ¡ver el trailer!

Math doesn't suck

En mi pasado viaje por San Francisco, en una de las librerías me encontré con esta gema.


Así es, un libro de matemáticas donde uno de los capítulos está titulado What's your Math Horoscope? Y continúa, para cada signo, dando una explicación sobre por qué, según la posición de los astros, deberías de hacer con muco gusto tu tarea de matemáticas.

Y, para que se puedan dar una idea de lo que se pueden encontrar en el resto del libro, esta es la portada.


Imaginemos por un momento a una niña de buenas intenciones pero un poco ingenua que se encuentra con este libro. Ella mira en la portada: do you still have a crush on him? “Wow! este libro de matemáticas me va a ayudar a saber si sigo enamorada de ese chico en la escuela!” La niña va entonces a buscar dentro del libro el artículo prometido y se encuentra con... ¡una lección sobre el máximo común divisor de dos números! “¿Wtf? ¿Y esto como me va a ayudar a saber si sigo enamorada? ¡Las matemáticas apestan!” diría nuestra amiga imaginaria, y yo estaría completamente de acuerdo con ella.

La verdad es que cuando me encontré yo con el libro no sabía como reaccionar. Yo adoro por supuesto las matemáticas, y admiro el hecho de que alguien esté tratando de hacer llamativo y accesible el estudiarlas. Pero esto, simplemente, es demasiado. ¿Horóscopos en un libro de matemáticas? Es como perder el punto totalmente.

De donas y videojuegos

Hoy me encontré en Brown Sharpire con una divertida “explicación” del toro, también conocido simplemente como “dona”, en términos de Pac-Man.


Para los no-matemáticos, observen que si toman una hoja de papel y pegan las orillas opuestas como indican las flechas en el dibujo de arriba, lo que obtienen en sus manos es precisamente una dona.

Esto me recordó también un dato geek/curioso sobre Tetrishpere ...


... y es que la “esfera” no es en realidad una esfera, sino una dona igual que en Pac-Man. De hecho no puede ser una esfera, porque una esfera no se puede cortar en “cuadritos” de manera uniforme. Observen por ejemplo que cuando la tierra se parte en paralelos y meridianos, en los polos no quedan cuadros, sino triángulos; y en las pelotas de fútbol se usan dos figuras, pentágonos y hexágonos, para poder partir “semi”-regularmente al balón.