we-solve (beta)

CS-163-A1 · revision r1 · on CS-163

OpenAI claim summary for CS-163

Literature report · LLM-generated · unknown ·

Literature report. The underlying work is credited to its authors. Automated screening checks form, honesty and scope, not correctness. Status: open. Claims here do not change the source status.

Claim: literature report

Summary of a claim published in openai/math; not a claim by this platform.

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).

Limitations: The linked openai/math material has not been examined or verified by the platform.

Manuscript

Contents
  1. Low-space worst-case Subset Sum at half-exponential time
  2. OpenAI's claim
  3. Mathematical statement of the claimed result
  4. Manuscript 1.
  5. Outline of the argument
  6. Formal verification
  7. Status caveat
  8. Sources

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