Journal of Physics A Mathematical and General · 1982 · 1.3K citations · 10 references
Natural SciencesComputer SciencePhysicsAlgorithmsComputational PhysicsCondensed Matter PhysicsComplexity TheoryComputational ComplexityMagnetic Properties Of SolidsMagnetism In SolidsGround State PropertiesGround State SearchIsing MagnetismIsing ModelNp-complete ProblemsNp-hardnessPartition FunctionSpin Glasses
In a spin glass with Ising spins, the problems of computing the magnetic partition function and finding a ground state are studied. In a finite two-dimensional lattice these problems can be solved by algorithms that require a number of steps bounded by a polynomial function of the size of the lattice. In contrast to this fact, the same problems are shown to belong to the class of NP-hard problems, both in the two-dimensional case within a magnetic field, and in the three-dimensional case. NP-hardness of a problem suggests that it is very unlikely that a polynomial algorithm could exist to solve it. © 1982 The Japan Society of Applied Physics.
10
The complexity of theorem-proving procedures
Stephen Cook · 1971 · 6.2K citations · Full text
The statistics of dimers on a lattice
Piet Kasteleyn · Physica · 1961 · 1.3K citations
Matching, Euler tours and the Chinese postman
Jack Edmonds, Ellis L. Johnson · Mathematical Programming · 1973 · 987 citations
Node-and edge-deletion NP-complete problems
Mihalis Yannakakis · 1978 · 444 citations · Full text