最坏情形子集和的一个低空间算法

最坏情形子集和的一个低空间算法

A Low-Space Algorithm for Worst-Case Subset Sum

OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。

具体内容

稿件给出最坏情形子集和的统一经典随机判定算法：在输入整数位长的任意固定多项式界下，每次执行使用poly(n)2^{n/2}时间与O(2^{n/5})个O(n+b)位可写字的普通空间，b为最大输入位长。错误为单侧：不可解实例总被拒绝，可解实例以至少2/3概率接受。研究意义在于同时控制时间与空间资源，给出最坏情形子集和的低空间随机算法。

• 每次执行时间为poly(n)2^{n/2}
• 使用O(2^{n/5})个O(n+b)位可写字空间
• 单侧错误：不可解必拒绝，可解以至少2/3概率接受

AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。

英文原始摘要

We give a uniform classical randomized decision algorithm for worst-case Subset Sum. Under every fixed polynomial bound on input-integer bit length, it uses $`\mathop{\mathrm{poly}}\nolimits (n)2^{n/2}`$ time and ordinary $`O(2^{n/5})`$ writable words of $`O(n+b)`$ bits, where b is the largest input bit length. Both resource bounds hold on every execution. The error is one-sided: the algorithm always rejects unsolvable instances and accepts each solvable instance with probability at least 2/3.

用户标记：未标记

固定编号：9c1655008a7ea06b