Jack Edmonds: la rivelazione della complessità ---------------------------------------------
Il matematico statunitense Jack Edmonds nacque nel 1934. Dopo gli studi entrò al National Bureau of Standards, dove lavorò sulla colorazione dei grafi, che rappresentava per mezzo di mappe e semispigoli. Tra la fine degli anni Cinquanta e l’inizio degli anni Sessanta, lo studio dei grafi passò dall’essere un campo di «problemi piacevoli e deliziosi» a una disciplina accademica (vedi Matematica discreta e Combinatoria, Biblioteca Tangente 39, 2009).
Claude Berge descrisse il metodo dei cammini alternanti per i problemi di accoppiamento di cardinalità massima. In un celebre congresso a Calgary, in Canada, presentò questo «algoritmo». Jack, in mezzo alla sala, si alzò e disse: «Claude it stinks your algorithm» («Puzza, il tuo algoritmo»). Per lo stesso problema Jack usò gli alberi alternanti e la dualità dei programmi lineari. I suoi alberi non sono affatto semplici: possono contenere cicli dispari, che contrae in un punto, e così via, arrivando a un algoritmo polinomiale. Il termine era stato coniato. Nella notte che precedette la sua relazione, volle generalizzare il proprio algoritmo alla ricerca di un insieme di vertici di un grafo, a due a due distinti e di cardinalità massima: è una generalizzazione del problema dell’accoppiamento. Ebbe una rivelazione: e se esistessero problemi per i quali non c’è alcun algoritmo polinomiale? Era nata la complessità degli algoritmi. Nel suo articolo Paths, Trees and Flowers descrisse il suo algoritmo di accoppiamento, poi fece una «digressione» (così chiamò il paragrafo in cui osservava che questa nozione di complessità è un autentico problema matematico).
Edmonds fu anche l’iniziatore degli approcci poliedrali, proponendo una descrizione completa del poliedro dell’accoppiamento. Risolse quindi un grandissimo numero di problemi combinatori polinomiali. Il problema del sottoinsieme indipendente comune a due matroidi e di cardinalità massima è un esempio dalla soluzione particolarmente elegante…
Vašek Chvátal -------------