La Visión se rinde ante un Problema del Milenio

En el #6 de La Visión de Tom King y Gabriel H. Walta (el último incluido en el primer tomo de la edición española de Panini) hay una discusión muy interesante sobre el problema P vs NP. No voy a entrar a discutir las cualidades de esta magnífica serie, ya que podéis consultar si os interesan las reseñas en la Zona Negativa aquí y aquí, e iré al grano. Cuelgo las tres páginas y la coda para que admiréis el dibujo de Walta, y por si os da pereza traducir o la imagen queda muy pequeña, traduzco el texto.

  1. Como pasa a menudo, aunque trate de complejidades, el problema en si mismo no es complejo.
  2. Para simplificarlo aun más, descartaré la nomenclatura y me concentraré en los conceptos.
  3. P representa problemas que un ordenador puede resolver en una cantidad razonable de tiempo. Por ejemplo, la multiplicación. Das dos números a un ordenador, le pides que los multiplique y obtienes la respuesta muy rápido.
  4. Para obtener dicha respuesta, el ordenador no comprueba todos lo números posibles que podrían encajar en la ecuación. Eso llevaría demasiado tiempo, de tantos números que hay.
  5. No, el ordenador untilizará un algoritmo, un método, un atajo. Resuelve el problema, no adivinando al azar sino mediante un proceso ordenado.
  6. Eso es P.
  7. Problemas que son prácticos. Problemas que, usando una especie de atajo, se pueden resolver.

  1. Existe, sin embargo, otro tipo de problema. Uno para el que no hay atajos.
  2. Estos problemas tienen solución. De hecho, si tienes una solución y le preguntas al ordenador si es correcta, el ordenador te dirá si lo es o no.
  3. Sin embargo, si pides al ordenador que resuelva el problema por ti… el ordenador, sin su atajo, simplemente comprobará un número prácticamente infinito de posibilidades hasta que tropiece con la correcta.
  4. Encontrar la respuesta llevará miles de millones de años a miles de millones de ordenadores.
  5. Esto es NP.
  6. Problemas que, a efectos prácticos, simplemente no se pueden resolver

  1. La gran pregunta sobre P y NP es si son de hecho una sola cosa
  2. ¿En realidad hay atajos para todos los problemas resolubles? ¿Es que simplemente no hemos descubierto todavía estos métodos esquivos, estos algoritmos perdidos?
  3. Y si eso es cierto, si todos los problemas NP son simplemente problemas P que esperan nuestra solución… entonces un ordenador podría resolver,  a falta de un término mejor, TODO.
  4. Todos los grandes secretos, desde las colisiones de átomos hasta las colisiones de galaxias, quedarían desvelados. Los veríamos. Serían nuestros.
  5. Por el contrario, si NP no es igual a P, entonces sencillamente hay problemas –problemas con soluciones– que los ordenadores no pueden resolver.
  6. Y como tales, dadas nuestras limitaciones, las grandes cuestiones de esta vida quedarían para siempre sin respuesta.

¿Qué hace esta descripción de P vs NP en este tebeo (por cierto, titulado eso, “P vs NP”)? Muy sencillo, la Visión quiere ser normal, quiere ser feliz, quiere que su esposa e hijos (no preguntéis) sean felices. Si la felicidad es un problema P, entonces debe de haber un algoritmo sencillo, un “atajo”, como lo llaman en el texto, que nos permita encontrarla. Pero no lo encuentra, y como predice Agatha Harkness en las últimas viñetas del tebeo, la Visión va a recurrir al enfoque indeterminista: va a probar y probar y probar lo que sea para intentar encontrar la felicidad para su familia. Y el desastre está asegurado. Hasta aquí os quiero contar.

Y como aún llego a tiempo, esta entrada también participa en la Edición 8.5 del Carnaval de Matemáticas cuyo anfitrión es Raíz de 2.

Advertisements

Con dos tiradas suele bastar

¿Quieres que nos juguemos el café? Mira, vamos a lanzar un dado por turnos e ir sumando los resultados que vayamos obteniendo. Gana el primero que con su tirada pase del número de caras del dado. Llevo mis dados de Magic en el bolsillo,  vamos a usar el de 20 para añadir un poco de emoción, así que ganará el primero que llegue a 20. ¿Vale? Empiezas tú. Tiras, sacas un 7, no llegas a 20. Tiro yo, saco un 6: 7+6=13, no llego a 20, tira. Sacas un 12: 13+12=25, ganas. ¡Mier…,!  ¡Uy, perdón, eso sí que no me lo esperaba! ¿Al mejor de tres?

(2 horas antes)

Estaba leyendo la autobiografía matemática de John Allen Paulos  y en un momento dado cita un artículo suyo en ABCnews  con apariciones estelares (la primera, literalmente) del número e. Una de ellas es, traduzco (y abrevio):

John Allen Paulos

Escoger números al azar también puede dar lugar a e. Elige un número entero aleatorio entre 1 y 1000. (Digamos que escoges 381.) Elige otro número aleatorio (digamos 191) y súmalo al primero (en este caso, da 572). Continua eligiendo números aleatorios entre 1 y 1000 y sumándolos a la suma de los números aleatorios escogidos previamente. Detente sólo cuando la suma supere los 1000. (Si el tercer número fuera 613, por ejemplo, la suma pasaría de 1000 después de tres selecciones.)

¿Cuántos números aleatorios, en promedio, necesitarás elegir? En otras palabras, si un grupo grande de personas repite este procedimiento, generar números entre 1 y 1000 y sumarlos hasta que la suma pase de 1000 y registrar el número de selecciones que han necesitado para llegar superar el 1000, el número promedio de dichas selecciones sería –lo has adivinado– muy próximo a e.

 

Pues sí, en la página del Wolfram Mathworld sobre la distribución de sumas de copias de una variable uniforme en [0,1] encontraréis la demostración de que si vais tomando números al azar entre 0 y 1 con distribución uniforme y sumándolos, la probabilidad de que la primera elección en la que la suma sea \geq 1 sea la n-ésima es 1/(n(n-2)!) y de que, entonces, la esperanza de esta distribución de probabilidades, es decir, el número promedio de números que tendremos que tomar para superar el 1, es e. Multiplicando por 1000, y quitando partes decimales, obtenéis la aproximación citada por Paulos.

Naturalmente, aunque lanzar un dado de N caras sea escoger un número entero al azar (y equiprobablemente) entre 1 y N, si N es pequeño entonces los decimales que se borran juegan un papel importante. Por ejemplo, con un dado de 6 caras, el número medio de lanzamientos necesarios para sumar 6 o més es un poco más de 2.16, y con un dado de 20 caras para superar el 20 necesitamos en promedio un poco más de 2.52. Con el dado de 100 caras que todos los matemáticos tenemos en casa rondamos el 2.68.

Pero hay otro dato que me interesa en el juego de tirar el dado y sumar hasta superar el umbral: si jugamos con un dado de N caras, más de la mitad de las veces llegaremos a N en la segunda tirada, independientemente de N. Esta probabilidad es muy sencilla de calcular: para pasar de N en la segunda tirada pero no en la primera, tenemos que sacar un k entre 1 y N-1 en la primera tirada y luego en la segunda cualquiera de los k+1 valores que hacen que la suma supere N (por ejemplo, si con un dado de 20 caras en la primera tirada saco un 5, para llegar a 20 en la segunda necesito algo entre 15 y 20). Por tanto, de las N^2 posibles tiradas dobles, en \sum\limits_{k=1}^{N-1} (k+1)=(N+2)(N-1)/2 pasaremos de N sin que en la primera tirada lleguemos a N, y este número es mayor que  N^2/2 si N\geq 3. En concreto, la probabilidad de superar N en dos tiradas de un dado de N caras es de aproximadamente 0.56 si N=4 o N=6; 0.53 si N=12; y 0.52 si N=20.

Así que en el jueguecito del principio, si dejamos empezar al otro, lo más probable es que ganemos en la segunda jugada, independientemente del dado. Y si no, siempre nos queda la cuarta, la sexta…

-Hola, Cesc, te veo muy concentrado

-¡Hola! Sí, estaba haciendo unos cálculos. Oye,  ¿quieres que nos juguemos el café? Mira, vamos a lanzar un dado por turnos…

Esta entrada participa en la Edición 8.5 del Carnaval de Matemáticas cuyo anfitrión es Raíz de 2.