{"id":"openai-math/A-Low-Space-Algorithm-for-Worst-Case-Subset-Sum","pdf":"https://github.com/openai/math/blob/main/preprints/A-Low-Space-Algorithm-for-Worst-Case-Subset-Sum-September-26-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/A-Low-Space-Algorithm-for-Worst-Case-Subset-Sum-September-26-2026","tags":["complexity-theory","subset-sum","algorithms"],"score":0,"title":"A Low-Space Algorithm for Worst-Case Subset Sum","domain":"Theoretical computer science","family":"138","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-26","reactions":{},"formalized":false,"family_title":"Subset Sum in $`O(2^{0.49n})`$ time"}