Application of statistical mechanics to NP-complete problems in combinatorial optimisation 论文

1986Journal of Physics A Mathematical and General引用 325

Computational Geometry and Mesh GenerationVLSI and FPGA Design TechniquesData Visualization and Analytics

VLSI and FPGA Design Techniques Data Visualization and Analytics Computational Geometry and Mesh Generation

作者

摘要

Recently developed techniques of the statistical mechanics of random systems are applied to the graph partitioning problem. The averaged cost function is calculated and agrees well with numerical results. The problem bears close resemblance to that of spin glasses. The authors find a spin glass transition in the system, and the low temperature phase space has an ultrametric structure. This sheds light on the nature of hard computation problems.

作者查看全部 (2)

Philip W. Anderson

Yuchen Fu

Application of statistical mechanics to NP-complete problems in combinatorial optimisation 论文

详细信息

摘要

作者查看全部 (2)

相关技术查看全部 (1)

相关事件

相关文章