Jack Edmonds: la revelación de la complejidad ---------------------------------------------
El matemático estadounidense Jack Edmonds nació en 1934. Tras sus estudios, ingresó en el National Bureau of Standards, donde trabajó en la coloración de grafos, que representaba mediante mapas y semiaristas. A caballo entre las décadas de 1950 y 1960, el estudio de los grafos pasó de ser un campo de «problemas agradables y deleitables» a convertirse en una disciplina académica (véase Mathématiques discrètes et Combinatoire, Bibliothèque Tangente 39, 2009).
Claude Berge describe el método de los caminos alternantes para problemas de emparejamiento de cardinalidad máxima. En un célebre congreso celebrado en Calgary (Canadá), presenta este «algoritmo». Jack, en mitad de la sala, se levanta y dice: «Claude it stinks your algorithm» («Tu algoritmo apesta, Claude»). Para este mismo problema, Jack utiliza los árboles alternantes y la dualidad de los programas lineales. Sus árboles no son precisamente sencillos: pueden contener ciclos impares, que «contrae» en un punto, y así sucesivamente, lo que le conduce a un algoritmo polinómico. La palabra está dicha. La noche anterior a su propia ponencia, quiere generalizar su algoritmo a la búsqueda de un conjunto de vértices mutuamente no adyacentes y de cardinalidad máxima; se trata de una generalización del problema del emparejamiento. Tiene una revelación: ¿y si existieran problemas para los que no hay algoritmo polinómico? La complejidad de los algoritmos acaba de nacer. En su artículo Paths, Trees and Flowers, describe su algoritmo de emparejamiento y, a continuación, hace una «digresión» (así llama al párrafo en el que menciona que esta noción de complejidad es un auténtico problema matemático).
Edmonds es también el impulsor de los enfoques poliédricos y propuso la descripción completa del poliedro del emparejamiento. Así resolvió un gran número de problemas combinatorios en tiempo polinómico. El problema del subconjunto independiente común a dos estructuras de matroides y de cardinalidad máxima es un ejemplo con una solución particularmente elegante…
Vašek Chvátal -------------