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