Illinois Genetic Algorithms Laboratory

April 1 (Urbana, IL). The Illinois Genetic Algorithms Laboratory (IlliGAL ) announced today that a simple genetic algorithm proved that P = NP.  Details of the surprising result will be published next month in the journal Complexity. Details released today indicate that a 20-node cluster computer running since the 1988 publication of Genetic Algorithms in Search, Optimization, and Machine Learning proved the theorem using a simple binary code, one-point crossover, no mutation, and proportionate selection (unscaled).  Surprisingly, the proof was only five steps away from Huffington's famous theorem (here).

    Lab director, Davy Goldberg was asked to comment and said the following: "This is really no big deal.  For a long time I've believed that complexity theorists were barking up a number of wrong trees, and the fact that such an early GA was able to derive the holy grail of that field should free up a number of faculty positions for individuals pursuing more creative research directions.  Personally, I'm more interested in the other 20-node cluster in IlliGAL that has been running since 1988 to evolve a computational consciousness.  If those designs are available in a few weeks, we're hoping that the resulting code can run for US president in 2008, given the dearth of viable candidates in both parties."

    Other researchers were approached for comment on the breakthrough. John Koza of Stanford and the Electoral College Fan Club said "The result is interesting, but I don't think it qualifies as human competitive because of criterion Q of the Hummie contest rules." Erik Goodman, chairman of SIGEVO and member of the bluegrass band The RFD Boys (Ann Arbor) hoped that the result would help unite the computational world and inspire some good newgrass music.  John Holland of the University of Michigan, Santa Fe Institute, and UP Butterfly Club said the he had developed a similar result at age six, but misplaced it during the move from West Engineering to North Campus over 20 years ago.

    For more information, as well as the formal proof, click here.