| Summary: | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mi mathvariant="normal">M</mi><mrow><mi>SAT</mi></mrow><mrow><mi mathvariant="normal">K</mi><mo>≥</mo><mn>3</mn></mrow></msubsup><mo> </mo></mrow></semantics></math></inline-formula> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mrow><mrow><mo> </mo><mi mathvariant="normal">M</mi></mrow></mrow><mrow><mi>SGI</mi></mrow><mrow><mn>3</mn><mi mathvariant="normal">D</mi></mrow></msubsup><mo> </mo></mrow></semantics></math></inline-formula> with the lattice size <i>N</i> = <i>mnl</i> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mi mathvariant="normal">M</mi><mrow><mi>AMC</mi></mrow><mrow><mn>3</mn><mi mathvariant="normal">D</mi></mrow></msubsup></mrow></semantics></math></inline-formula> 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 Z<sub>2</sub> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi mathvariant="normal">C</mi><mi mathvariant="normal">L</mi></msub><mfenced><mrow><msubsup><mi mathvariant="normal">M</mi><mrow><mi>SGI</mi></mrow><mrow><mn>3</mn><mi mathvariant="normal">D</mi></mrow></msubsup></mrow></mfenced><mo> </mo></mrow></semantics></math></inline-formula> is the computational complexity by brute force search of the AMC model <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi mathvariant="normal">C</mi><mi mathvariant="normal">U</mi></msup><mfenced><mrow><msubsup><mi mathvariant="normal">M</mi><mrow><mi>AMC</mi></mrow><mrow><mn>3</mn><mi mathvariant="normal">D</mi></mrow></msubsup></mrow></mfenced></mrow></semantics></math></inline-formula>, the lower bound of the computational complexity of the K-SAT problem for K ≥ 4 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi mathvariant="normal">C</mi><mi mathvariant="normal">L</mi></msub><mfenced><mrow><msubsup><mi mathvariant="normal">M</mi><mrow><mi>SAT</mi></mrow><mrow><mi mathvariant="normal">K</mi><mo>≥</mo><mn>4</mn></mrow></msubsup></mrow></mfenced><mo> </mo></mrow></semantics></math></inline-formula> is the computational complexity by brute force search of the K-SAT problem for K = 3 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mrow><mrow><mo> </mo><mi mathvariant="normal">C</mi></mrow></mrow><mi mathvariant="normal">U</mi></msup><mfenced><mrow><msubsup><mi mathvariant="normal">M</mi><mrow><mi>SAT</mi></mrow><mrow><mi mathvariant="normal">K</mi><mo>=</mo><mn>3</mn></mrow></msubsup></mrow></mfenced></mrow></semantics></math></inline-formula>. Namely, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi mathvariant="normal">C</mi><mi mathvariant="normal">L</mi></msub><mfenced><mrow><msubsup><mi mathvariant="normal">M</mi><mrow><mi>SAT</mi></mrow><mrow><mi mathvariant="normal">K</mi><mo>≥</mo><mn>4</mn></mrow></msubsup></mrow></mfenced><mo>=</mo><msub><mi mathvariant="normal">C</mi><mi mathvariant="normal">L</mi></msub><mfenced><mrow><msubsup><mi mathvariant="normal">M</mi><mrow><mi>SGI</mi></mrow><mrow><mn>3</mn><mi mathvariant="normal">D</mi></mrow></msubsup></mrow></mfenced><mo>≥</mo><msup><mi mathvariant="normal">C</mi><mi mathvariant="normal">U</mi></msup><mfenced><mrow><msubsup><mi mathvariant="normal">M</mi><mrow><mi>AMC</mi></mrow><mrow><mn>3</mn><mi mathvariant="normal">D</mi></mrow></msubsup></mrow></mfenced><mo>=</mo><msup><mi mathvariant="normal">C</mi><mi mathvariant="normal">U</mi></msup><mfenced><mrow><msubsup><mi mathvariant="normal">M</mi><mrow><mi>SAT</mi></mrow><mrow><mi mathvariant="normal">K</mi><mo>=</mo><mn>3</mn></mrow></msubsup></mrow></mfenced></mrow></semantics></math></inline-formula>. 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.
|
|---|