All Questions
Tagged with statistical-physics np-complete
2 questions
8
votes
2
answers
1k
views
Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?
In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks.
Isn't it straight forward to ...
- 463
2
votes
0
answers
349
views
Which complexity information of Ising model is more important?
In 1982, Barahona proved that finding the ground state of an Ising model is NP-hard. Later, in 2000, Istrail proved that it is NP-complete. When I look up the citations of these two papers using ...
- 661