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

DOI10.1007/BF01721098zbMATH Open0625.90070MaRDI QIDQ580185FDOQ580185

Authors: Jianyong Qiao, Sumit K. Garg 

Publication date: 1987

Published in: OR Spektrum (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenessfrustration modelspin-glasses

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• 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)