we-solve (beta)

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

Exponential Algorithms for Knapsack

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

The input is a list of integers $a_1,\ldots,a_n,b$, encoded in binary. The decision problem specified by the source is subset sum: \[ \exists (x_1,\ldots,x_n)\in\{0,1\}^n\quad \sum_{i=1}^n a_ix_i=b. \] Each list position can be used at most once; equal integer values may appear in different positions. The empty selection is allowed. Although the source calls this knapsack, there is no additional profit objective or inequality capacity constraint.

Let $L$ be the total bit length of the input, including signs. The algorithmic target is a uniform exact worst-case algorithm using \[ O(2^{n/3}L^c) \] bit operations for some absolute constant $c$, on every input. This states the source's exponential rate while making the omitted cost of reading and handling large integers explicit. No space bound is imposed. Deterministic algorithms are the baseline interpretation; any randomized variant must state its error and time guarantees separately. A faster method that works only for random or specially structured integer lists does not meet the universal worst-case target. The problem is to achieve this running time or to establish a rigorously specified obstruction in an explicit computational model.

Short English statement

Can arbitrary binary-encoded subset-sum instances on n integers be solved exactly in time two to the n/3 times a polynomial in the input length?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 2

CS-87-A2 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for CS-87

The new randomized algorithm has exponent $0.49$ for polynomial-bit Subset Sum inputs. The problem requires a deterministic exponent-one-third target with the broader encoded-input scope; the advertised improvement reaches neither that exponent nor that model.

Exponential Algorithms for Knapsack

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-10-04), the asserted result is that bounded-error classical Subset Sum on polynomial-bit inputs has a uniform $O(2^{0.49n})$ algorithm with that bound on every random execution.

Mathematical statement of the claimed result

Manuscript 1.
For positive integers $a_1,\ldots,a_n$, nonnegative target $t$ and $n\ge2$, ask whether $\sum_{i\in I}a_i=t$ for some subset. Put $b=\max\{1,\lceil\log_2(1+\max(t,a_1,\ldots,a_n))\rceil\}$ and use the stated word-RAM with read-only input and $w=\lceil4(n+b+\log_2(n+2))\rceil$-bit words; all preprocessing, addressing, word arithmetic and random generation are charged. The claimed single uniform randomized algorithm halts on every execution, is correct with probability at least $2/3$ on every input, and obeys \[ \forall c\ge1\ \exists C_c,N_c\ \forall n\ge N_c,\ b\le n^c: \quad T\le C_c2^{0.49n} \] word operations on every random path. The program is independent of the fixed polynomial bit-length exponent $c$.

Outline of the argument

For manuscript 1 (family 138; 2026-10-04), filtered representations recover modular aliases through small digit lists. Input-independent pair scores satisfy weighted Fourier-moment bounds, and checksum estimation combines direct sums with importance sampling; deterministic caps control both the visited lists and numerical work.

Formal verification

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

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 →

CS-87-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on CS-87

Exponential Algorithms for Knapsack

Definitions and mathematical statement

The input is a list of integers $a_1,\ldots,a_n,b$, encoded in binary. The decision problem specified by the source is subset sum: \[ \exists (x_1,\ldots,x_n)\in\{0,1\}^n\quad \sum_{i=1}^n a_ix_i=b. \] Each list position can be used at most once; equal integer values may appear in different positions. The empty selection is allowed. Although the source calls this knapsack, there is no additional profit objective or inequality capacity constraint.

Let $L$ be the total bit length of the input, including signs. The algorithmic target is a uniform exact worst-case algorithm using \[ O(2^{n/3}L^c) \] bit operations for some absolute constant $c$, on every input. This states the source's exponential rate while making the omitted cost of reading and handling large integers explicit. No space bound is imposed. Deterministic algorithms are the baseline interpretation; any randomized variant must state its error and time guarantees separately. A faster method that works only for random or specially structured integer lists does not meet the universal worst-case target. The problem is to achieve this running time or to establish a rigorously specified obstruction in an explicit computational model.

Short English statement

Can arbitrary binary-encoded subset-sum instances on n integers be solved exactly in time two to the n/3 times a polynomial in the input length?

Research attempt

Scope and process.
GPT-6 Astra Ultra, 2 October 2026. The canonical formulation above is retained. This attempt uses a primary-source literature audit, independent restricted proofs, and adversarial checks. Reproved results are not claimed as new. Numerical tests below are reproducible in scripts/check_attempt_batch03_extremal_2026_10_02.py.
Literature and computational model.
Chen, Jin, Randolph and Servedio [S3] give polynomial-factor savings over $2^{n/2}$ in specified RAM models, with randomized one-sided-error algorithms. Their paper distinguishes these savings from improving the constant in the exponential exponent. Neither those model-specific savings nor average-case algorithms supply the catalogue's deterministic exact $2^{n/3}\operatorname{poly}(L)$ bit bound. We audit two deterministic reductions that attain the requested rate on explicit restricted families and identify the missing combination step in the naive three-way split.
The exact baseline, including signed inputs.
Split the list positions into two blocks of sizes $\lfloor n/2\rfloor,\lceil n/2\rceil$. Enumerate their subset sums as lists $A,B$. Sort $B$ and, for every $a\in A$, test membership of $b-a$ in $B$ by binary search. Every full subset decomposes uniquely into subsets of the two blocks, so this decides the original question exactly. Equal sum values may be merged without changing existence. Signed entries cause no problem: no positivity-based pruning is used. Each sum has $O(L+\log n)$ bits, and additions, sorting comparisons and searches cost a polynomial in $L$. The resulting worst-case bound is $2^{n/2}\operatorname{poly}(L)$, not the requested exponent.
A range-sensitive sufficient condition.
Let $g$ be the greatest common divisor of the nonzero entries. If there are no nonzero entries, the answer is precisely $b=0$. Otherwise $g\nmid b$ immediately gives a no-instance; if it divides, divide all entries and $b$ by $g$. Write $W=\sum_i|a_i|$ for the new entries. Start with $S_0=\{0\}$ and update \[ S_i=S_{i-1}\cup\{s+a_i:s\in S_{i-1}\}. \] Induction shows that $S_i$ is exactly the set of sums using the first $i$ positions once each. Store it as a Boolean row indexed by $[-W,W]$, using the old row when updating. This costs $O(nW\operatorname{poly}(L))$ bit operations. Thus the target rate holds whenever the normalized $W$ is at most $2^{n/3}$ times a fixed polynomial in $L$. Binary input does not ensure this: even one entry can have value exponential in its bit length.
Compressing multiplicities without losing solutions.
Suppose a nonzero value $v$ occurs $m$ times. Choose chunks $1,2,4,\ldots$ greedily until the remainder is no larger than the next power of two, then use that remainder as the final chunk. These positive chunks sum to $m$, and each is at most one plus the sum of its predecessors. By induction, their subset sums comprise every integer from zero to $m$: adding a chunk $c\le s+1$ to an already covered interval $[0,s]$ gives overlapping or adjacent intervals $[0,s]$ and $[c,c+s]$. Replace the $m$ copies of $v$ by the chunk multiples of $v$.

Exactly $\lceil\log_2(m+1)\rceil$ chunks suffice. Every old selection count has a chunk representation, and every new selection count is at most $m$, so attainable sums are unchanged in both directions. Negative values obey the same count argument; zero entries can be discarded. If nonzero multiplicities are $m_1,\ldots,m_s$, the compressed length is \[ N'=\sum_{j=1}^s\lceil\log_2(m_j+1)\rceil. \] The baseline now takes $2^{N'/2}\operatorname{poly}(L)$ time, meeting the desired rate when $N'\le2n/3$. The condition fails for lists with all distinct values, so it is a restricted theorem.

Verification and the first general gap.
The script compares attainable sums before and after compression and against dynamic programming on every signed list of length at most five over $\{-2,-1,0,1,2\}$. It also checks every multiplicity through 25. Splitting arbitrary positions into three equal blocks does produce three lists of size $2^{n/3}$, but joining two lists explicitly takes up to $2^{2n/3}$ pairs. For each entry of the third list, a two-list scan similarly gives that larger cost. This diagnoses that construction, not a lower bound against all algorithms. An exact faster joining method, or a universally applicable structural reduction, remains missing.
Final status.
The target rate holds under the stated range or multiplicity conditions. Arbitrary binary lists remain UNRESOLVED by this attempt.

Sources

Go to contribution →