子集和问题的时间O(2^{0.49n})算法
Subset Sum in Time $`O(2^{0.49n})`$
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件研究子集和问题的精确算法。摘要称给出一个统一随机经典算法，在多项式比特输入的字RAM模型下具有有界错误，最坏情况运行时间为O(2^{0.49n})，其中n为输入整数个数；该时间界在每次随机执行中都成立。若成立，这将改进子集和问题的指数时间上界。这是AI产生的研究手稿，收录不表示已完成独立审查或同行评议。
- 给出子集和问题的统一随机经典算法，具单边有界错误。
- 最坏情况运行时间为O(2^{0.49n})，n为输入整数个数。
- 时间界在每次随机执行中均成立。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We give a uniform randomized classical algorithm for Subset Sum with bounded error and worst-case running time $`O(2^{0.49n})`$ on polynomial-bit inputs in a word-RAM model, where n is the number of input integers. The time bound holds on every random execution.
用户标记：未标记
固定编号：39f0a7ad584c0c7c
原文来源