论文标题
解决完美总和问题的概率方法
A Probabilistic Approach to The Perfect Sum Problem
论文作者
论文摘要
众所周知，子集总和问题是计算机科学领域中的NP硬问题，其运行时复杂性为$ O（2^{0.3113N}）$。此问题的修改版本称为完美的总和问题，并进一步扩展了子集总和。此扩展会导致额外的复杂性，因此很难计算出大型输入。在本文中，我提出了一种概率方法，该方法通过近似于电势总和的分布来近似于完美总和问题的解决方案。由于此问题是子集总和的扩展，因此我们的近似值还对子集总和问题的解决方案进行了一些概率洞察力。我们利用分布近似值来建模总和到一定大小的子集的数量。这些分布近似以两种方式制定：使用边界来证明正常近似合理，并通过密度估计来近似经验分布。这些近似值可以以$ o（n）$复杂性计算，并且可以随输入数据的大小而提高准确性，从而使其对大规模组合问题有用。代码可从https://github.com/kristofpusztai/perfectsum获得。
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.
