The subset sum problem is known to be an NP-hard problem in the field of computer science with the fastest known approach having a run-time complexity of $O(2^{0.3113n})$. A modified version of this problem is known as the perfect sum problem and extends the subset sum idea further. This extension results in additional complexity, making it difficult to compute for a large input. In this paper, I propose a probabilistic approach which approximates the solution to the perfect sum problem by approximating the distribution of potential sums. Since this problem is an extension of the subset sum, our approximation also grants some probabilistic insight into the solution for the subset sum problem. We harness distributional approximations to model the number of subsets which sum to a certain size. These distributional approximations are formulated in two ways: using bounds to justify normal approximation, and approximating the empirical distribution via density estimation. These approximations can be computed in $O(n)$ complexity, and can increase in accuracy with the size of the input data making it useful for large-scale combinatorial problems. Code is available at https://github.com/KristofPusztai/PerfectSum.
翻译:子数问题在计算机科学领域被认为是一个NP-硬性的问题,以已知速度最快的方法,其运行时间复杂度为O(2 ⁇ 0.3113美元)美元。这个问题的修改版本被称为完美总和问题,进一步扩展子数概念。这一扩展导致更加复杂性增加,难以计算大量投入。在本文件中,我提议一种概率方法,通过接近潜在金额的分配来接近完美总和问题的解决办法。由于这是子数的延伸,我们近似也为子数问题的解决方案提供了某种概率洞察力。我们利用分配近似值来模拟子数的数量,而子数则达到一定的大小。这些分布近似以两种方式拟订:使用界限来证明正常近似,通过密度估计来接近经验分布。这些近似值可以用美元(n)的复杂度来计算,并随着输入数据的规模的精确度而提高,从而对大规模组合问题有用。 代码可在 https://Psimus/commith. http://Kforporm.