El professor Babai dóna un pas més en la demostràció que P=NP
Origen: Un informático teórico logra “el descubrimiento de la década” en su campo – MIT Technology Review
El professor László Babai de la Universitat de Chicago (EUA) va donar dues ponències d’una sèrie de tres que descriuen la seva nova solució per a un problema anomenat l’isomorfisme de grafs. L’Isomorfisme de grafs és un problema de la categoria P. Si la nova solució rebaixa la complexitat a NP aleshores es podria haver demostrat que P=NP. Si això es demostra tots els criptogràfics actuals (entre ells els d’Internet) s’haurien de repensar, ja que voldria dir que hi hauria una solució fàcil per desencriptar les comunicacions.
El problema d’informàtica teòrica P=NP és un dels anomenats problemes del mil·leni i està valorat en un milió de dòlars.
