we-solve (beta)

CS-163 · computer science · mathematics · Algorithms and data structures

Low-space worst-case Subset Sum at half-exponential time

Status OpenLLM status Open unverified

Statement

Definitions and mathematical statement

Statement recorded in the supplied source.
For positive-integer Subset Sum with n items and bit length $b\leq n^c$ for any fixed c, can one uniform randomized classical word algorithm use $n^{O_c(1)}2^{n/2}$ operations and $O_c((n+b+2)^{15}2^{0.199n})$ writable words on every path, never falsely answering YES and answering YES instances correctly with probability $\geq 2/3$, without being given c?

Short English statement

For positive-integer Subset Sum with n items and bit length $b\leq n^c$ for any fixed c, can one uniform randomized classical word algorithm use $n^{O_c(1)}2^{n/2}$ operations and $O_c((n+b+2)^{15}2^{0.199n})$ writable words on every path, never falsely answering YES and answering YES instances correctly with probability $\geq 2/3$, without being given c?

Sources

Statement licence: CC-BY-4.0 · Source file

Contributions 1

CS-163-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for CS-163

The result supplies the conclusion in this problem with its displayed hypotheses and quantifiers. The broader statements and applications in the manuscript are kept separate from the particular question above. The supporting result is manuscript 1 (family 138; 2026-09-26).

Low-space worst-case Subset Sum at half-exponential time

OpenAI's claim

OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 138; 2026-09-26), the asserted result is that worst-case Subset Sum has a one-sided randomized solver in $\operatorname{poly}(n)2^{n/2}$ time and $O(2^{n/5})$ ordinary writable words on every execution.

Mathematical statement of the claimed result

Manuscript 1.
The input comprises positive integers $a_1,\ldots,a_n$ and a nonnegative integer $t$, with $n\ge2$; the question is whether $\sum_{i\in I}a_i=t$ for some subset $I$. Define \[ b=\max\{1,\lceil\log_2(1+\max(t,a_1,\ldots,a_n))\rceil\},\qquad w=\lceil4(n+b+\log_2(n+2))\rceil. \] The model has read-only random-access input and counted writable $w$-bit words, unit-cost word arithmetic and addressing, and unit-cost fresh random words; all stored randomness and preprocessing are charged. A single uniform algorithm has no false positive and accepts each positive instance with probability at least $2/3$. For every fixed integer $c\ge1$ there exist $A_c,k_c,N_c$ such that $n\ge N_c$ and $b\le n^c$ imply, on every random execution, \[ T\le A_c n^{k_c}2^{n/2},\qquad S\le A_c(n+b+2)^{15}2^{0.199n} \] in operations and writable words, respectively. The algorithm itself does not depend on $c$.

Outline of the argument

For manuscript 1 (family 138; 2026-09-26), distinct-sum counts and entropy estimates select between two trials. Compact block dictionaries generate larger representation lists through small-state streams, while bounded random-prime sampling and exact word operations preserve the time, storage, and one-sided guarantees.

Formal verification

No Lean formalization is listed at this snapshot for manuscript 1 (family 138; 2026-09-26).

This site has not executed the Lean code. Described statement coverage is not an independent proof check.

Status caveat

The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.

Sources

Go to contribution →