More about NP-completeness in the frustration model of spin-glasses

DOI10.1007/BF01721098MaRDI QIDQ580185zbMATH OpenFDO

Authors Jianyong Qiao, Sumit K. Garg

Publication date 1987

Published in OR Spektrum (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01721098

zbMATH Keywords

frustration modelNP-completenessspin-glasses

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Review text

It is pointed out that a recent proof [see \textit{C. P. Bachas}, J. Phys. A17, 1709-1712 (1984)] of the NP-completeness of determining the ground state of spin-glasses is missing an important step. We fill in the step omitted by the author and in the process find that a stronger theorem can be proved.

Recommendations

• Approximability of the ground state problem for certain Ising spin glasses
• scientific article; zbMATH DE number 1342099
• Determining computational complexity from characteristic ``phase transitions
• The complexity of analog computation
• Application of statistical mechanics to NP-complete problems in combinatorial optimisation

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Node-and edge-deletion NP-complete problems

Cited in

(1)

• Towards a theory of frustrated degeneracy.

This page was built for publication: More about NP-completeness in the frustration model of spin-glasses

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q580185)