Computational complexity of the ground-state determination of atomic clusters
- 1 June 1985
- journal article
- Published by IOP Publishing in Journal of Physics A: General Physics
- Vol. 18 (8) , L419-L422
- https://doi.org/10.1088/0305-4470/18/8/003
Abstract
The authors prove that determining the ground state of a cluster of identical atoms, interacting under two-body central forces, belongs to the class of NP-hard problems. This means that as yet no polynomial time algorithm solving this problem is known and, moreover, that it is very unlikely that such an algorithm exists. It also suggests the need for good heuristics.Keywords
This publication has 16 references indexed in Scilit:
- Computer-intractability of the frustration model of a spin glassJournal of Physics A: General Physics, 1984
- Equilibrium Geometries and Electronic Structures of Small Sodium ClustersPhysical Review Letters, 1984
- On the statistical mechanics of optimization problems of the travelling salesman typeJournal de Physique Lettres, 1984
- An application of physical methods to the computer aided design of electronic circuitsJournal de Physique Lettres, 1984
- Optimization by Simulated AnnealingScience, 1983
- On the computational complexity of Ising spin glass modelsJournal of Physics A: General Physics, 1982
- On the ground states of the frustration model of a spin glass by a matching method of graph theoryJournal of Physics A: General Physics, 1980
- Structure and Dynamics of Simple MicroclustersAdvances in Chemical Physics, 1979
- Independence results in computer scienceACM SIGACT News, 1976
- Statistical mechanics and morphology of very small atomic clustersFaraday Discussions of the Chemical Society, 1976