Lower bound of computational complexity of knapsack problems

Abstract

The quantum statistics mechanism is very powerful for investigating the equilibrium states and the phase transitions in complex spin disorder systems. The spin disorder systems act as an interdisciplinary platform for solving the optimum processes in computer science. In this work, I determined the lower bound of the computational complexity of knapsack problems. I investigated the origin of nontrivial topological structures in these hard problems. It was uncovered that the nontrivial topological structures arise from the contradictory between the three-dimensional character of the lattice and the two-dimensional character of the transfer matrices used in the quantum statistics mechanism. I illustrated a phase diagram for the non-deterministic polynomial (NP) vs polynomial (P) problems, in which a NP-intermediate (NPI) area exists between the NP-complete problems and the P-problems, while the absolute minimum core model is at the border between the NPI and the NP-complete problems. The absolute minimum core model of the knapsack problem cannot collapse directly into the P-problem. Under the guide of the results, one may develop the best algorithms for solving various optimum problems in the shortest time, being in subexponential and superpolynomial. This work illuminates the road on various fields of science ranging from physics to biology to finances, and to information technologies.

40 pages, 7 figures

References in corpus (10)

• Conjectures on exact solution of three - dimensional (3D) simple orthorhombic Ising lattices
• Critical behavior of the van der Waals bonded ferromagnet Fe${}_{3-x}$GeTe${}_2$
• Clifford algebra approach of 3D Ising model
• Computational complexity of spin-glass three-dimensional (3D) Ising model
• Ground-state behavior of the 3d +/-J random-bond Ising model
• Solving NP-hard problems with bistable polaritonic networks
• Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem
• Logic Integer Programming Models for Signaling Networks
• Dynamic Asset Allocation with Expected Shortfall via Quantum Annealing
• Computational Characteristics of Random Field Ising Model with Long-Range Interaction

Cited by in corpus (3)

• Exact solution of the three-dimensional (3D) Z2 lattice gauge theory
• Exact solution of a two-dimensional (2D) Ising model with the next nearest interactions
• Equivalence between the zero distributions of the Riemann zeta function and a two-dimensional Ising model with randomly distributed competing interactions