Y he aquí que (como todos los buenos homosexuales), Alan Turing fue al cielo después de suicidarse. Suerte para él que justo por la fecha de su muerte las cortes celestiales derogaran la ley que condenaba al infierno por toda la eternidad a los suicidas, cambiándola por la nueva ley que los pone al nivel de mártires en los casos en que fueron orillados al suicidio por la incomprensión la sociedad que, para mala suerte de ellos, les tocó.
El cielo se parece mucho a la Tierra, sólo que todo mundo habla el mismo idioma (aunque no se da cuenta uno), y en el caso de los homosexuales (como Turing) tienen orgías amistosas todos los martes a las 9 donde se escucha música de The Village People. Cuando llegó Turing no existían todavía The Village People; pero compensaban con mambos de Pérez Prado (tenían que arreglárselas como pudieran).
Los primeros 20 años en su estadía en el cielo, Turing acudió regularmente a las orgías de los martes a las 9, hizo deporte (que no es necesario, porque todos tienen un físico perfecto en el cielo, pero pues a Turing le gustaba), y se dedicó a leer literatura, escuchar música (además de Pérez Prado) y ver teatro y cine. En el cielo, cada quien en su casa tiene una pantalla de materia divina de 200 pulgadas donde pueden ver lo que sea, desde la programación del canal 5 hasta cualquier acontecimiento público (en el cielo son muy respetuosos de la privacidad de los mortales en la Tierra). Y por supuesto se entiende siempre no importa el idioma que hablen los que estén enfocados por la pantalla.
Después de 20 años de orgías y enriquecimiento cultural, Turing decidió ver qué transa con el avance de la ciencia en la Tierra. La Biblioteca Universal del Cielo tiene todos los escritos de la humanidad; en el momento en que algo es escrito en la Tierra, una copia aparece en la BUC, desde las cartas de amor más ridículas de niños de primaria, hasta el evangelio de Jesús, donde Jesús expresa que cuando el les decía se amaran los unos a los otros, jamás dijo que “excepto hombres con hombres”. Y si no, que le preguntarán a San Pedro, que no consiguió chamba de portero nomás por su barba. Al menos no nada más.
Después de enterarse del Teorema de Cook-Levin, Turing decidió que probar si NP ≠ P era suficientemente interesante como para entretenerse unas cuantas décadas, y se metió de lleno al problema. Sin dejar de ir a las orgías de los martes a las 9, claro, uno tiene que distraerse.
Sin embargo, pasaron un par de décadas y Turing no avanzaba en la demostración. Seguía con mucho detenimiento los progresos de sus colegas mortales; la BUC funciona un poco como la Wikipedia, uno puede tener un “watch list”, y cada elemento puede ser un tema completo. Sólo que la notificación es un querubín molesto que toca una campanita en el oído del “watcher” cada vez que algo nuevo se publica respecto al tema.
Deberían ver los dolores de cabeza de los que ponen en su “watch list” al tema “pornografía”; un error de novatos en el cielo. ¿Comenté que la BUC también es videoteca, hemeroteca, audioteca, y karateka?
Por fin un día el querubín molesto tocó la camapanita en el oído de Turing, y después de mandarlo volar contra una pared de un manotazo, Turing salió corriendo a la BUC (lo cual es una expresión; en el cielo la distancia de cualquier punto a cualquier otro es siempre la constante de 73 centímetros… y no queda muy claro por qué 73 centímetros), y leyó con avidez la prueba de que se había encontrado una cota inferior en el tiempo de ejecución para un algoritmo NP-completo.
La cota inferior era de n2.
Turing hizo cachitos el artículo y salió mentando literalmente madres de la BUC, mientras los cachitos se reparaban solos en el artículo (también se duplican automáticamente si dos personas quieren el mismo texto al mismo tiempo). Turing fue con San Pedro (se llevaban bien; se conocieron en las orgías de los martes a las 9) y exigió una audiencia con Dios.
San Pedro le dijo lo que generalmente decía a los que pedían audiencia con Dios: “uy joven, eso está cabrón”, y le explicó la complicada agenda del grandote. “El universo no se expande solo”, explicó.
Turing le dijo que no se hiciera pendejo, que él sabía que Dios era omnipotente y que eso incluía la capacidad de estar en dos lugares al mismo tiempo, y que usaba la excusa de la expansión del universo porque (admitámoslo) qué hueva estar oyendo las dudas de todos los que están en el cielo… que son más de lo que el común de la gente podría creer.
Nada más había terminado de decir eso, cuando Dios apareció y dijo lo que generalmente dice cuando se materializa (porque siempre está ahí) ante seres humanos:
“Quihubo”.
Dios, muchos no lo saben, suele tomar la forma de una mujer absurdamente sabrosa con poquísima ropa; por suerte para Turing él era homosexual, así que no se distrajo y le dijo sin ni siquiera parpadear: “te tengo una pregunta”.
Dios inclinó la cabeza como meditando la cuestión (le encanta el drama), y le dijo: “va, pero sólo una pregunta”.
“¿Es NP igual a P?”, preguntó Turing.
Dios inclinó la cabeza (al otro lado), y le dijo:
“No”.
Después de lo cual se dio la media vuelta y empezó a caminar, moviendo sensualmente las caderas.
“¡Pero…!”, empezó a gritar Turing, y Dios se volteó para mirarlo y le dijo: “Te dije que sólo una“. Y se desvaneció mientras caminaba meneando las caderas (le encantanlos tacones de 15 centímetros a Dios; qué mejor uso de la omnipotencia que el poder verse sexy sin que al otro día te duelan las plantas de los pies).
Desde ese día Turing sigue yendo a las orgías de los martes a las 9, volvió a leer, ver cine y teatro, y de vez en cuando trabaja en cosas de matemáticas, sólo para pasar el rato. Se hizo cuate de Erdős y han estado trabajando en varias cosas, pero en el fondo Turing quiere convencerlo de que lo acompañe a una de las orgías de los martes a las 9; depués de leer “The Man Who Loved Only Numbers”, Turing está convencido de que Erdős es de ambiente.
Me suena el apellido, es el tipo de las famosas Maquinas de Turing??? Mi maestro ( un matemático antisocial y soltero ) mencionó un día que se había suicidado porque era gay, pero yo no sabía si era verdad o no jaja. Discfruté la historia :D
Él es el de las famosas Máquinas de Turing. No se suicidó por ser gay; la policía lo encarceló porque descubrieron que era gay cuando en Inglaterra era ilegal, y lo obligaron a llevar una “terapia” hormonal para que se “curara”. Además, Turing era alguien importante en las investigaciones en criptografía y otras cosas relacionadas con los servicios de inteligencia británicos; todos sus privilegios fueron revocados a raíz de su arresto.
No es algo divertido: la humanidad perdió una de sus más grandes mentes por la intolerancia de la sociedad en que le tocó vivir. Tenía 42 años.
Pero, wow Canek, la forma en que lo escribes es buenísima, el cielo, jajajaja, Pérez Prado!!!
Dios qué divertido. No entendí nada de lo de NP=P pero eso no quita lo agradable y divertido del texto.
Estoy igual que Olimpia… pero lo de Pérez Prado no tiene madres jajajajaja
Hijole Canek ¿de cual fumas?
Ta muy chida la historia, me gustó eso de la constante de 73 cms que se aplica en el cielo… y lo de karateka…
Pero bueno, es bastante obvio que P != NP… o tu que piensas?
La cosa es que realmente tenemos tan poca información al respecto, que bien podría darse que P = NP. No es completamente descabellado, por ejemplo, que existiera un algoritmo polinomial que resuelva un problema NP-completo, pero que el grado del polinomio sea 1,000,000,000,000.
Entonces ya tendríamos un algoritmo que nos colapsaría NP en P; pero para todos los motivos prácticos la clase NP sigue siendo intratable.
Lo que quiero decir es que no es tan “obvio”. Hay mucha gente mucho más lista que yo que lleva décadas trabajando en eso, y lo más que han logrado son cosas como la cota inferior de n2 para ciertos problemas NP-completos.
Independientemente de (como dice el Dr. Sergio Rajsbaum del IMATE) la vergonzosa situación al respecto, lo cierto es que tal vez no importe. Si el DNA-Computing o la computación cuántica o ve tú a saber qué otra cosa se materializa (y no se ve realmente lejano), este tipo de máquinas harían tratables todos los problemas NP-completos.
Y aún si no se materializaran, como dijo el Dr. Davies en la plática que dio el semestre pasado en CU, ¿qué importa? Todo mundo menciona al problema del agente viajero cuando comienza a hablar de problemas NP-completos… y todo computólogo que se respete ha resuelto el TSP. No de forma óptima, pero sí con muy buenas aproximaciones, ya sea usando algoritmos probabilísticos, o redes neuronales o algoritmos genéticos.
Yo en lo particular creo que NP ≠ P, pero realmente hablo de lo que mis tripas me dicen; bien podría darse que fuera lo contrario.
No se me ponga tan serio… era sarcasmo =P
Si NP fuese igual a P… y despues de tanto tiempo dedicado al asunto, tal vez alguien hubiese encontrado algo mas que la cota inferior para CIERTOS problemas NP-completos.
Ah, pero es que ese es el chiste de las matemáticas. El que después de tanto tiempo dedicados al asunto no se haya encontrado nada más que algunas cotas inferiores no demuestra nada… excepto que necesitamos saber más.
Claro que es posible que NP = P. A lo mejor no muy probable, pero ciertamente posible.
La computación cuántica NO va a poder resolver problemas NP. Hasta la fecha son pocos (4 ó 5) problemas muy específicos los que parece que van a poder resolverse mucho mas rápido que con las computadoras actuales (como la factorización de enteros), pero como las operaciones cuánticas son operaciones lineales, se cree que el conjunto de problemas que podrá resolver será estrictamente menor que NP.
Por cierto, esta entrada está buenísima, ojalá te dé por escribir ficción más seguido.
Juan: la cosa con los problemas NP-completos, es que con uno que resuelvas en tiempo polinomial, resuelves todos los demás en tiempo polinomial. Tienes reducciones polinomiales para todos los problemas NP-completos (esa es su definición).
Si resuelves factorizar enteros en tiempo polinomial, te resuelvo cualquier otro problema NP-completo en tiempo polinomial. El aspecto práctico es otra cosa (qué grado tendría el polinomio, qué tan grande puede ser la entrada a resolver, etc.), pero el modelo sí colapsa NP en P.
1. Tu definición es un poco imprecisa, con uno que resuelvas tienes reducciones polinomiales para todos los problemas NP (no nomás para los NP-completos)
2. No se ha probado que factorizar enteros sea NP-completo (y se cree que NO es)
1. Te equivocas de nuevo: si demuestras que un problema p está en NP, pero no que es NP-completo, entonces por definición no tienes una reducción polinomial a otro problema NP-completo (si la tuvieras p sería NP-completo). Entonces no puedes resolver p con tu computadora cuántica.
(Podría ser que p ∈ P, pero ese caso es irrelevante, ya que puedes resolverlo en tiempo polinomial para empezar).
2. Pero se cree que es más difícil, no más fácil. Entonces seguro puede colapsar NP en P.
Por ejemplo, el problema “¿tiene n un factor menor que m?” es NP-completo; y seguro factorizar enteros debe poder resolverlo en tiempo polinomial.
Juan me recordó que justamente el Teorema de Church-Turing es justamente que cualquier problema en NP se puede reducir polinomialmente a SAT. Entonces si podemos resolver un problema NP completo, podemos resolver cualquier problema NP.
Y además investigando más a fondo, resulta que el problema “¿tiene n un factor menor que m?” no es NP-completo (o eso se cree), aunque sí está en NP (yo había leído mal la explicación del problema). No es más difícil; de hecho es menos difícil que todos los NP-completos.
Así que una computadora cuántica no colapsaría (o al menos no se ha demostrado) NP en P.