Parte I, La vida es difícil.
Todos
sabemos lo importante que son los computadores en el mundo moderno (qué haríamos sin Facebook o Twitter!!). Usando supercomputadores (Fig 1)
los científicos están intentando resolver preguntas, que van desde cómo
se formaron las primeras estructuras en el universo, pasando por el
desarrollo de nuevas drogas, el plegamiento de proteínas, la búsqueda de
nuevos materiales, la simulación del cerebro humano y un largo
etcétera.
Esta
columna es la primera parte de una serie donde hablaremos sobre el
siguiente paso en la revolución computacional, que de ser exitosa dejará
a los supercomputadores tradicionales como máquinas obsoletas; los computadores cuánticos!. Pero primero, algo de contexto.
La
capacidad de análisis que tenemos a nuestra disposición gracias a los
computadores es impresionante. Los supercomputadores más potentes que
existen hoy día pueden realizar del orden de 10^15 (esto es
1.000.000.000.000.000 o mil billones) operaciones por segundo. La
capacidad de procesamiento en un smartphone hoy es millones de veces
mayor que el sistema que guío el Apolo 11 a la Luna!!. Esta capacidad de
cálculo nos permite enfrentarnos a problemas que de otra manera serían
intratables. Por ejemplo, para entender la aparición de las galaxias, actualmente científicos están recreando las
condiciones del universo desde el big bang hasta hoy en día [1],
estudiando la distribución de materia (observable y oscura) en el universo. Otro interesante proyecto, basado en el poder de
cálculo de los computadores actuales, es el proyecto sobre el cerebro
humano [2], donde usando redes de computadores, se intentará tener un
modelo del funcionamiento del cerebro, simulando la conexión entre las
distintas neuronas, entre otras cosas.
Figura 1. Supercomputadores de Paine
A
pesar de poseer esta capacidad de análisis, existen problemas que son
prácticamente imposibles de resolver por los computadores actuales. Esto
se debe a que la solución de estos problemas requiere la búsqueda en un
espacio de posibilidades inmensamente grande. Un ejemplo simple es el
siguiente. Supongamos que tienes que ir a comprar pan, pasar a pagar la
cuenta de la luz, visitar a tus padres, y salir a carretear (de fiesta),
todo esto viajando en bicicleta. No importa el orden en que visites los
lugares (Fig 2). Lo natural es planear cuál es la ruta más óptima, en
la cual tienes que recorrer menos distancia. Suena simple ¿no?. Este
problema se conoce como el problema del vendedor viajero.
La dificultad aparece cuando la cantidad de lugares a visitar aumenta.
Supongamos que la cantidad de lugares a visitar es N. El método más
simple para buscar el recorrido más corto es elegir un lugar, luego
elegir un lugar entre los restantes, y así sucesivamente hasta agotar
los lugares. Para cada elección tendremos un camino, y podemos comparar
la distancia recorrida. Así, si tenemos que visitar 4 lugares, las
posibilidades son: elegimos el primer lugar de entre 4 candidatos,
quedan 3. Por cada elección anterior podemos elegir tres restantes, asi
que tenemos 4X3=12 posibilidades, y quedan 2. Repitiendo la lógica,
deberemos revisar 4X3X2X1=24 posibilidades (Fig. 3).
Resulta
que este método implica revisar N factorial posibilidades. N factorial
(se denota N con un signo de exclamación, N!) es el número que resulta
de multiplicar todos los números enteros entre 1 y N, así
5!=5x4x3x2x1=120.
Revisa por ti mism@ cuanto es por ejemplo 20!, y te darás cuenta por qué el signo de exclamación es adecuado**.
Figura 2. En la práctica, probablemente no quieras llegar con una bolsa de pan al carrete, a menos que sea un asado.
Figura 3. La cantidad de distintas posibilidades de elegir una secuencia de 4 elementos distintos es 4!=24.
Revisando
cuán difícil es encontrar la solución a un problema, podemos separar
los problemas en varios tipos. Los problemas en los cuales, dados N
datos (o entradas) la solución se puede encontrar realizando N^s (N
elevado a s, para algún número s fijo) operaciones, se clasifican como
problemas de tipo P (P porque la solución se encuentra en tiempo
polinomial en el numero de entradas y la función N elevado a s
en matemáticas se conoce como un polinomio). Por ejemplo encontrar el
número más grande entre una lista de números es un problema tipo P, dado
que tenemos que realizar N-1 comparaciones para encontrar el número
mayor entre N números. Este ejercicio lo haces cada vez que miras por el
item que salió más caro en la compra del supermercado. Todos los
problemas de este tipo, conforman la clase P.
Podemos pensar en estos problemas como problemas “Fáciles de resolver”.
Por otro lado, están los problemas para los cuales la verificación de
la solución es polinomial. Estos problemas pertenecen a la clase NP (polinomial no determinístico).
Un
ejemplo de problema NP es el problema del vendedor viajero, que
discutimos anteriormente. Podemos pensar en estos problemas como
problemas donde, dada una posible solución, esta se puede verificar
fácilmente. ¿Confundid@?, un ejemplo nos ayudará a entender. Supongamos
que te doy un número de teléfono, y te pido que busques a quien
pertenece este número de teléfono. Tú vas a la guia de teléfonos y luego
de revisar todos los números, das con el nombre del dueño de ese número
telefónico. Quizás para los más jóvenes es necesario recordar que la
Guía de teléfonos (la de papel) está ordenada por nombres, pero no por
números de teléfono. Así que encontrar un nombre es fácil, ya que uno
solo busca alfabéticamente. Pero buscar por número de teléfono es
complicado, ya que estos no estań ordenados.
Podrás
imaginar que encontrar la solución es complicado (tuviste que revisar
un directorio telefónico completo!). Si ahora tú vas y le preguntas a
otra persona: ¿Es el número 00-000000 el teléfono de el señor Tocino?,
la respuesta es simple, dado que esa persona sólo tiene que ir y buscar
por el señor Tocino en el directorio, y comparar el número telefónico
que allí aparezca con el dado. Este es un ejemplo de un problema donde
encontrar la solución es mucho más complicado que verificar si cierta
solución es válida.
Recapitulando,
tenemos problemas fáciles, (clase P) y problemas donde, dada cierta
posible solución, es fácil verificar si ese candidato es en realidad
solución (clase NP).
El
problema de la guía de teléfonos es NP, pero también es P, dado que
encontrar la solución es fácil en términos computacionales, y solo toma
un tiempo proporcional al número de personas incluidas en el directorio
telefónico. Decimos que la clase NP contiene a la clase P. Esto
significa que todos los problemas tipo P son tipo NP, pero no todos los
problemas NP son necesariamente tipo P. Un gran problema abierto en
Matemáticas y ciencias de la computación es probar (o refutar) que las
clases P y NP son distintas. Aunque no hay una demostración, creemos que
estas clases son en realidad distintas, ya que hay problemas tipo NP
donde encontrar una solución es realmente difícil.
Los
problemas tipo NP incluyen muchos problemas interesantes y cuya
solución puede ser muy útil, como en logística, planeamiento de
ciudades, o secuenciación de ADN por nombrar unos pocos. Es en este tipo
de problemas donde los computadores actuales son ineficientes y donde
un computador cuántico sería útil, ya que volvería estos problemas
“fáciles”.
Pero ¿qué rayos es un computador cuántico?, y ¿cómo transforma problemas difíciles en problemas fáciles?
Respuestas a estas preguntas, en una siguiente entrada de el tocino.
Manténganse atentos.
*Cuático
es un chilenismo con muchos significados. Aquí se usa como
impresionante.
** 20!=2.432902e+18. 80! es un número mayor que
el número de átomos en el universo!!
No hay comentarios.:
Publicar un comentario