Problema del Milenio 1: P contra NP

NP contra P - Parte 1: La algoritmia como ciencia y arte

El "gran problema" de un ingeniero informático es poder encontrar un algoritmo eficiente para cualquier problema(valga la redundancia) de la vida real y que éste pueda ser computado por una máquina determinada(de Turing) consiguiendo un correcto funcionamiento y de forma que éste verifique una posible solución. La algoritmia es la ciencia que estudia técnicas para diseñar algoritmos eficientes y evaluar la eficacia de estos.

Apunto la palabra "ingeniero" debido a que en este ámbito (el de análisis y diseño de algorítmos y estudio de la complejidad computacional) es la palabra más apropiada según muchos puntos de vista, lo cual no desbanca a aficionados, académicos o autodidactas interesados en el estudio de este arte/ciencia que es la algoritmia.

Para el que no comprenda muchas de estas cosas, empezaré con un simple problema del Profesor G.B Dantzig:
Supongamos que queremos asignar 70 trabajos a 70 personas. Las limitaciones de este problema son que cada persona debe ser asignada a cualquier trabajo y que por tanto cada trabajo debe ser ocupado.

Esta clarísimo. Cualquiera que tenga ciertas nociones sobre combinatoria habrá observado que se trata de un simple conteo de permutaciones, o lo que es lo mismo, ¿cuantas formas tenemos de asignar 70 tareas a 70 personas? La respuesta: 70! (factorial de 70) asignaciones.
Aquí haré un pequeño paréntesis para explicar algunas cosas:
Un algoritmo, dicho rápidamente, es una serie de reglas o pasos que realizan un conjunto de acciones para resolver un problema. Así, p.e., un algoritmo puede ser los pasos a dar en la suma de dos numeros o incluso aquellos que damos al freir un huevo. Un programa informático cualquiera, en cambio, es una colección de líneas codificadas que, una máquina determinada es capaz de interpretar y en base a ellas, realizar automáticamente una serie de cálculos que pueden o no reflejar algún resultado.
Volviendo al problema de antes. Si estuvieramos en una clase de matemáticas, ciertamente la respuesta sería la que he puesto arriba(70! asignaciones). Pero en términos computacionales dicha afirmación es algo absurdo. Esto es porque 70! es un numero muy grande (mayor que 10 elevado a 100) y realizar tantas asignaciones en un bucle repetitivo resulta un agotamiento extremo de los recursos computacionales. Veamos este caso: Supongamos que tenemos un ordenador capaz de examinar mil millones de asignaciones por segundo. Si lo tuviéramos trabajando sobre las 70! asignaciones desde el mismo instante del "Big Bang", hace 15 mil millones de años, hoy en día aún no habría terminado los cálculos. Incluso si la Tierra estuviera cubierta de ordenadores de esas características, todos trabajando en paralelo, la respuesta seguiría siendo no. Sólo en el caso de que dispusieramos de 10 elevado a 50 Tierras, o 10 elevado a 44 Soles, todos recubiertos por ordenadores de velocidad del nano segundo, todos programados en paralelo, trabajando desde el mismo instante del Big Bang hasta el día en que ocurra el enfriamiento del Sol, entonces quizás la respuesta fuera sí.
Aquí es donde entra en juego el poder de la algoritmia. Bajo estrategias bien fundadas basadas en el diseño de algoritmos, se puede ejercer un impacto eficaz sobre la resolución de problemas. De una forma hábil y magistral se puede analizar cualquier algoritmo, estudiando su complejidad y buscando, en cualquier caso, el algoritmo más eficiente. Esto se consigue teniendo una cierta capacidad de visión sobre cómo están ordenados los datos en su naturaleza y, atajando, mediante enfoques ingeniosos pudiendo ser mencionados "de artista", la dificultad que un problema de cualquier tipo pueda ofrecernos.
Un conocido Algoritmo Húngaro resuelve el problema de la asignación de tareas en menos de nueve minutos, en contraposición de lo escrito anteriormente, y viene a demostrar la conveniencia y economía del estudio de la algoritmia, así como del desarrollo de algoritmos basados en sus procedimientos y metodologías.

En efecto, la contrucción de un algoritmo es un arte que nunca debiera automatizarse, sino sobre el que más bien hay que intervenir para favorecer, por el contrario, que a partir del estudio serio y riguroso de sus técnicas, como ocurre con las mejores creaciones artísticas, se logren obras de valor, mérito y reconocimiento mundial.

"En la vida sólo hay siete grandes problemas que no podemos resolver, el más complicado es el de vivir."

Juan David Valencia Castro