Survey on computational complexity with phase transitions and extremal optimization

Applying statistical mechanics to search problems in AI, decisions and optimization has been one of the powerful channels to solve NP-hard problems. Extensive analytical and experimental research has shown that the ¿phase transition¿ phenomenon in search space is often associated with the hardness of complexity. A Bak-Sneppen (BS) model based general-purpose heuristic method, called extremal optimization (EO), proposed by Boettcher and Percus from physics society may perform very well, especially near the phase transitions in compared with other optimization methods, e.g., genetic algorithm and simulated annealing, etc. To actuate more extensive investigations on this new optimization approach particularly in control, computer and optimization communities, this survey reviews the latest research results from fundamental to practice about the connection between computational complexity and phase transitions. Then, further introduces the concepts, fundamentals, algorithms and applications of EO from its capability of self-organized criticality, backbone analysis and co-evolution moving to a far-from-equilibrium state. Finally, the concluding remarks with suggested future research are illustrated.