Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem

Zhidong Zhang

doi:10.3390/math11010237

journal article Open Access Jan 03, 2023

Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem

Zhidong Zhang

Mathematics Vol. 11 No. 1 pp. 237 · MDPI AG

View at Publisher Save 10.3390/math11010237

Abstract

The common feature for a nontrivial hard problem is the existence of nontrivial topological structures, non-planarity graphs, nonlocalities, or long-range spin entanglements in a model system with randomness. For instance, the Boolean satisfiability (K-SAT) problems for K ≥ 3 MSATK≥3 are nontrivial, due to the existence of non-planarity graphs, nonlocalities, and the randomness. In this work, the relation between a spin-glass three-dimensional (3D) Ising model MSGI3D with the lattice size N = mnl and the K-SAT problems is investigated in detail. With the Clifford algebra representation, it is easy to reveal the existence of the long-range entanglements between Ising spins in the spin-glass 3D Ising lattice. The internal factors in the transfer matrices of the spin-glass 3D Ising model lead to the nontrivial topological structures and the nonlocalities. At first, we prove that the absolute minimum core (AMC) model MAMC3D exists in the spin-glass 3D Ising model, which is defined as a spin-glass 2D Ising model interacting with its nearest neighboring plane. Any algorithms, which use any approximations and/or break the long-range spin entanglements of the AMC model, cannot result in the exact solution of the spin-glass 3D Ising model. Second, we prove that the dual transformation between the spin-glass 3D Ising model and the spin-glass 3D Z2 lattice gauge model shows that it can be mapped to a K-SAT problem for K ≥ 4 also in the consideration of random interactions and frustrations. Third, we prove that the AMC model is equivalent to the K-SAT problem for K = 3. Because the lower bound of the computational complexity of the spin-glass 3D Ising model CLMSGI3D is the computational complexity by brute force search of the AMC model CUMAMC3D, the lower bound of the computational complexity of the K-SAT problem for K ≥ 4 CLMSATK≥4 is the computational complexity by brute force search of the K-SAT problem for K = 3 CUMSATK=3. Namely, CLMSATK≥4=CLMSGI3D≥CUMAMC3D=CUMSATK=3. All of them are in subexponential and superpolynomial. Therefore, the computational complexity of the K-SAT problem for K ≥ 4 cannot be reduced to that of the K-SAT problem for K < 3.

Topics

No keywords indexed for this article. Browse by subject →

References

59

[1]

Beitrag zur Theorie des Ferromagnetismus

Ernst Ising

Zeitschrift für Physik 1925 10.1007/bf02980577

[2]

Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition

Lars Onsager

Physical Review 1944 10.1103/physrev.65.117

[3]

Zhang "Conjectures on the exact solution of three-dimensional (3D) simple orthorhombic Ising lattices" Phil. Mag. (2007) 10.1080/14786430701646325

[4]

Clifford algebra approach of 3D Ising model

Zhidong Zhang, Osamu Suzuki, Norman H. March

Advances in Applied Clifford Algebras 2019 10.1007/s00006-018-0923-2

[5]

Suzuki, O., and Zhang, Z.D. (2021). A method of Riemann-Hilbert problem for Zhang’s conjecture 1 in a ferromagnetic 3D Ising model: Trivialization of topological structure. Mathematics, 9. 10.3390/math9070776

[6]

Zhang, Z.D., and Suzuki, O. (2021). A method of the Riemann-Hilbert problem for Zhang’s conjecture 2 in a ferromagnetic 3D Ising model: Topological phases. Mathematics, 9. 10.3390/math9222936

[7]

Zhang "Mathematical structure of the three-dimensional (3D) Ising model" Chin. Phys. B (2013) 10.1088/1674-1056/22/3/030513

[8]

Zhang "The nature of three dimensions: Non-local behavior in the three-dimensional (3D) Ising model" J. Phys. Conf. Ser. (2017) 10.1088/1742-6596/827/1/012001

[9]

Marchiafava "An approach to models of order-disorder and Ising lattices" Adv. Appl. Clifford Alg. (2010) 10.1007/s00006-010-0219-7

[10]

Suzuki "On the ternary approach to Clifford structures and Ising lattices" Adv. Appl. Clifford Alg. (2012) 10.1007/s00006-012-0360-6

[11]

Suzuki "Fractals and chaos related to Ising-Onsager-Zhang lattices versus the Jordan-von Neumann-Wigner procedures. Quaternary approach, Inter" J. Bifurc. Chaos (2012) 10.1142/s0218127412300030

[12]

Suzuki "Fractals and chaos related to Ising-Onsager-Zhang lattices. Quaternary Approach vs. Ternary Approach" Adv. Appl. Clifford Alg. (2012)

[13]

Wegner "Duality in generalized Ising models and phase transitions without local order parameters" J. Math. Phys. (1971) 10.1063/1.1665530

[14]

Mastering the game of Go with deep neural networks and tree search

David Silver, Aja Huang, Chris J. Maddison et al.

Nature 2016 10.1038/nature16961

[15]

Zhang "Computational complexity of spin-glass three-dimensional (3D) Ising model" J. Mater. Sci. Tech. (2020) 10.1016/j.jmst.2019.12.009

[16]

Cook, S. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, Shaker Heights, OH, USA, 3–5 May 1971; ACM: New York, NY, USA.

[17]

Levin "Universal search problems (Russian: Универсальные задачи перебoра, Universal’nye perebornye zadachi). Problems of Information Transmission (Russian: Прoблемы передачи инфoрмации" Probl. Peredachi Inf. (1973)

[18]

Protein Folding in the Hydrophobic-Hydrophilic ( HP ) Model is NP-Complete

Bonnie Berger, TOM LEIGHTON

Journal of Computational Biology 1998 10.1089/cmb.1998.5.27

[19]

Blondel "A survey of computational complexity results in systems and control" Automatica (2000) 10.1016/s0005-1098(00)00050-9

[20]

Fortune "The directed subgraph homeomorphism problem" Theor. Comput. Sci. (1980) 10.1016/0304-3975(80)90009-2

[21]

Kfivfinek "NP-hard problems in hierarchical-tree clustering" Acta Inform. (1986) 10.1007/bf00289116

[22]

Krentel "The complexity of optimization problems" J. Comput. Syst. Sci. (1988) 10.1016/0022-0000(88)90039-6

[23]

Lewis "The node-deletion problem for hereditary properties is NP-complete" J. Comput. Syst. Sci. (1980) 10.1016/0022-0000(80)90060-4

[24]

Mundici "Satisfiability in many-valued sentential logic is NP-complete" Theor. Comput. Sci. (1987) 10.1016/0304-3975(87)90083-1

[25]

Murty "Some NP-complete problems in quadratic and nonlinear programming" Math. Program. (1987) 10.1007/bf02592948

[26]

Papadimitriou "The Euclidean traveling salesman problem is NP-complete" Theor. Comput. Sci. (1977) 10.1016/0304-3975(77)90012-3

[27]

Papadimitriou, C.H. (1994). Computational Complexity, Addison-Wesley.

[28]

Paszkiewicz, A., and Węgrzyn, J. (2020). Responsiveness of the sensor network to alarm events based on the Potts model. Sensors, 20. 10.3390/s20236979

[29]

Peeters "The maximum edge biclique problem is NP-complete" Discrete Appl. Math. (2003) 10.1016/s0166-218x(03)00333-0

[30]

Poljak "Checking robust nonsingularity is NP-hard" Math. Control Signals Syst. (1993) 10.1007/bf01213466

[31]

Tovey "A simplified NP-complete satisfiability problem" Discrete Appl. Math. (1984) 10.1016/0166-218x(84)90081-7

[32]

Barahona "On the computational complexity of Ising spin glass models" J. Phys. A (1982) 10.1088/0305-4470/15/10/028

[33]

Barahona "Morphology of ground states of two-dimensional frustration model" J. Phys. A (1982) 10.1088/0305-4470/15/2/033

[34]

Istrail, S. (2000, January 21–23). Universality of Intractability for the Partition Function of the Ising Model Across Non-Planar Lattices. Proceedings of the 32nd ACM Symposium on the Theory of Computing (STOC00), Portland, OR, USA.

[35]

A variational description of the ground state structure in random satisfiability problems

G. Biroli, R. Monasson, M. Weigt

The European Physical Journal B 2000 10.1007/s100510051065

[36]

Franz "Replica bounds for optimization problems and diluted spin systems" J. Stat. Phys. (2003) 10.1023/a:1022885828956

[37]

Mora "Clustering of solutions in the random satisfiability problem" Phys. Rev. Lett. (2005) 10.1103/physrevlett.94.197205

[38]

Spin Glass Theory and Beyond

M Mezard, G Parisi, M Virasoro

World Scientific Lecture Notes in Physics 10.1142/0271

[39]

RandomK-satisfiability problem: From an analytic solution to an efficient algorithm

Marc Mézard, Riccardo Zecchina

Physical Review E 2002 10.1103/physreve.66.056126

[40]

Monasson "Statistical mechanics of the random K-satisfiability model" Phys. Rev. E (1997) 10.1103/physreve.56.1357

[41]

Weigt "Simplest random K-satisfiability problem" Phys. Rev. E (2001) 10.1103/physreve.63.026702

[42]

Zhang "Exact solution of two-dimensional (2D) Ising model with a transverse field: A low-dimensional quantum spin system" Phys. E (2021) 10.1016/j.physe.2021.114632

[43]

Spin glasses: Experimental facts, theoretical concepts, and open questions

K. Binder, A. P. Young

Reviews of Modern Physics 1986 10.1103/revmodphys.58.801

[44]

Theory of spin glasses

S F Edwards, P W Anderson

Journal of Physics F: Metal Physics 1975 10.1088/0305-4608/5/5/017

[45]

Infinite-ranged models of spin-glasses

Scott Kirkpatrick, David Sherrington

Physical Review B 1978 10.1103/physrevb.17.4384

[46]

Solvable Model of a Spin-Glass

David Sherrington, Scott Kirkpatrick

Physical Review Letters 1975 10.1103/physrevlett.35.1792

[47]

Stein, D.L., and Newman, C.M. (2010). Spin Glasses and Complexity, Princeton University Press.

[48]

Kaufman "Crystal Statistics II: Partition function evaluated by spinor analysis" Phys. Rev. (1949) 10.1103/physrev.76.1232

[49]

Lou "Three-dimensional Ising model and transfer matrices" Chin. J. Phys. (2000)

[50]

Perk "Comment on ‘Conjectures on exact solution of three-dimensional (3D) simple orthorhombic Ising lattices’" Phil. Mag. (2009) 10.1080/14786430902776970

Showing 50 of 59 references

Metrics

16

Citations

59

References

Details

Published: Jan 03, 2023
Vol/Issue: 11(1)
Pages: 237
License: View

Authors

Z

Zhidong Zhang

Shenyang National Laboratory for Materials Science, Institute of Metal Research, Chinese Academy of Sciences, 72 Wenhua Road, Shenyang 110016, China

Funding

National Natural Science Foundation of China Award: 52031014

Cite This Article

Zhidong Zhang (2023). Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem. Mathematics, 11(1), 237. https://doi.org/10.3390/math11010237

Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem

You May Also Like