In recent years, there has been a great progress in computer science, specially, in machine learning, artificial intelligence, data mining, and so on, which changes our daily life. The computational complexity of NP-complete problems is the most fundamental problem in computer science. In computational complexity theory, NP is an abbreviation for non-deterministic polynomial time, which is defined as the set of decision problems that can be solved in polynomial time on a non-deterministic Turing machine. A P-problem can be solved in polynomial time by a deterministic Turing machine. In NP, the set of all decision problems whose solutions can be verified in polynomial time are cataloged to NP-complete problems. The K-satisfiability (K-SAT) problem for K ≥ 3 is a central problem in combinatorial optimization. The K-SAT problem deals with an ensemble of N Boolean variables, submitted to M constraints. Each constraint is expressed in the form of an OR function of K variables (or their negations) in the ensemble, and the problem is to check whether there exists one configuration (among 2N possible ones) of the variables, which satisfies all constraints.
In a recent work published in Mathematics, Prof. ZHANG Zhidong from Institute of Metal Research, Chinese Academy of Sciences (IMR, CAS), determined the lower bound of computational complexity of the Boolean Satisfiability Problem.
Prof. ZHANG Zhidong started his work from another NP-complete problem, the spin-glass 3D Ising model. At first, he proved that the absolute minimum core (AMC) model 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. This character determines the lower bound of the computational complexity of the spin-glass 3D Ising model to be subexponential and superpolynomial.
Then, Prof. ZHANG Zhidong proved that the spin-glass 3D Ising model can be mapped to the K-SAT problem for K ≥ 4, by the duality between the 3D Ising model and the 3D Z2 gauge lattice theory and the consideration of random interactions and frustration. Thus, the lower bound of the computational complexity of the Boolean satisfiability problem for K ≥ 4 is also in subexponential and superpolynomial. Furthermore, he proved that the AMC model of the spin-glass 3D Ising model is equivalent to the K-SAT problem for K = 3. The computational complexity of the K-SAT problem for K ≥ 4 cannot be reduced to that of the K-SAT problem for K < 3. The present work provides a bridge between mathematics, computer science, and physics, which enhances understanding and efficiency of solutions of related problems.
