Computing the Partition Function of the Sherrington-Kirkpatrick Model is Hard on Average
© 2020 IEEE. We establish the average-case hardness of the algorithmic problem of exactly computing the partition function of the Sherrington-Kirkpatrick model of spin glasses with Gaussian couplings. In particular, we establish that unless P=#P, there does not exist a polynomial-time algorithm to e...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2022
|
| Online Access: | https://hdl.handle.net/1721.1/144132 |