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)

zbMATH Keywords

NP-completenessfrustration modelspin-glasses

Mathematics Subject Classification ID

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

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)