``NP\(=\)P?'' and restricted partitions (Q799370)

Let \(A=\{a_ 1,a_ 2,...,a_ p,...\}\) be a set of natural numbers and s a given integer. If n can be expressed by \[ (1)\quad n=x_ 1a_ 1+x_ 2a_ 2+...+x_ pa_ p+..., \] where \(x_ 1,x_ 2,...,x_ p,...\) are nonnegative integers satisfying \[ (2)\quad s=x_ 1+x_ 2+...+x_ p+..., \] then the expression (1) with restriction (2) is called an s-restricted partition of n about A. The number of s-restricted partitions of n about A is denoted by R(n,A,s). This paper establishes a relationship between partition theory and the tractability of NP-complete problems. In fact, we have proved the following Theorem. If there exists a series of sets \(A_ n=\{P_{1n},P_{2n},...,P_{nn}\}\) with \(P_{in}\leq n^ s\) for \(i=1,2,...,n, n=1,2,3,...,\) such that \(R(\sum^{n}_{i=1}P_{in},A_ n,n)\leq n^ k\), \(n=1,2,3,...,\) where k and s are constants independent of n, then \(NP=P\). In validating the conclusion we propose a dynamic programming algorithm, with a set of natural numbers as its parameters, whose time complexity depends on the restricted partition property of this set.