Seminario del Laboratorio de Aplicaciones Matemáticas (LAM)

Resumen:

Hasta la mitad del siglo XX los métodos numéricos se dividían en dos partes. Los métodos iterativos y los métodos finitos. Los primeros eran métodos que garantizaban convergencia a un punto con ciertas características. Importaba, y sigue importando, la velocidad de convergencia. Los segundos, como la eliminación Gaussiana, encontraban, teóricamente, la inversa de una matriz en un número finito de pasos. Desde luego el segundo tipo de métodos era preferible.

Justo a la mitad del siglo pasado, Dantzig inventa el método Simplex y demuestra que termina en un número finito de pasos. El método Simplex se convierte en uno de los métodos más usados y exitosos de la Investigación de Operaciones. Poco después, Gomory desarrolla el método de planos cortantes para Programación Entera y prueba que termina en un número finito de pasos. La expectativa era que fuera igual de eficiente que el Simplex, pero desafortunadamente no fue así.

En la década de los 60´s varios investigadores proponen teorías de complejidad computacional para problemas combinatorios. Estas teorías se basan en el reconocimiento de que la garantía de que un método termine en un número finito de pasos no es una buena medida de eficiencia. Proponen entonces clasificar a los algoritmos como “buenos” si el número de pasos no es solo finito, sino que además está acotado polinomialmente, como la inversión de matrices que requiere aproximadamente pasos.

En contraste, los algoritmos que para alguna instancia requieran un número exponencial de pasos se clasifican como “malos”.

Estas ideas dan origen al paradigma actual de la complejidad computacional basado en las clases, y que ha prevalecido en los últimos 50 años.

En esta plática expondré con detalle lo dicho en este resumen y haré énfasis en algunas anomalías de este paradigma usando como marco de referencia el esquema propuesto por Thomas Kuhn en su libro “La estructura de las revoluciones científicas”.

También bosquejaré algunas ideas para tratar de encontrar un paradigma más adecuado.