Testing perfect graphs. Famous people (Lovasz, Knuth, ...) conjectured in the 1980s that there is a polynomial time recognition for perfect graphs. Such an algorithm was found after almost 20 years later by famous people ( Cornuéjols and other, FOCS 2003).