基于联立丢番图逼近的子集和问题启发式求解算法

Heuristic Algorithm for the Subset Sum Problem based on Simultaneous Diophantine Approximation

子集和问题是计算机科学中的一个重要问题,也被应用于公钥密码和伪随机函数的设计.学界已提出多个求解一般子集和问题的通用求解算法及求解特定子集和问题的特殊求解算法.本文通过建立子集和问题和联立丢番图逼近问题之间的联系,提出一种新的子集和问题启发式求解算法.该算法由给定的子集和问题构造联立丢番图逼近问题,使用格归约算法寻找该联立丢番图逼近问题的解,由此构造与原始子集和问题线性无关的新的子集和问题,从而达到降低原始子集和问题维数的目的;最后,通过n-1个联立丢番图逼近问题的解来构造n—1个线性无关的子集和问题,并通过求解一个由n个变量和n个线性方程构成的方程组来求解原始子集和问题.基于联立丢番图逼近的子集和问题启发式求解算法为子集和问题研究提供了新的思路.

The subset sum problem is one of the most significant problems in computer science,and the problem has been used in designing public key cryptographic schemes and pseudorandom functions due to the NP-completeness nature. Therefore, the study of the subset sum problem is of important significance in both computer science and cryptography. Under the basic P≠ NP hypothesis, there must exist no polynomial-time algorithms to solve the subset sum problem. Some general-purpose algorithms for solving generic subset sum problems and special-purpose algorithms for solving special subset sum problems have been proposed in the literature. This paper proposes a novel heuristic algorithm for solving the subset sum problem by establishing a connection between the subset sum problem and the simultaneous Diophantine approximation problem. The basic idea of the proposed algorithm is to firstly construct simultaneous Diophantine problems from the given subset sum problem, then find the solutions to the simultaneous Diophantine problems via lattice reduction algorithms, construct new subset sum problems independent of the original subset sum problem and from the solutions to the simultaneous Diophantine problems, ultimately reduce the dimension of the original subset sum problem. Finally, the binary solution to the original subset sum problem is determined by solving an n-variable system of n linear equations, which is derived from n — 1 linearly independent subset sum problems constructed by solving simultaneous Diophantine approximation problems. The significance of the new approach in this paper provides new insights into the subset sum problem.