Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

論文872 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/872 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。

本文はサイトの記事でも読めます（2026年10月7日 12:20 に公開します）。

@misc{yamagishi2026yoi872,
  author = {Yamagishi, Yuuki},
  title = {The Table That Solves Subset Sum Grows with the Size of the Numbers, Not with Their Count},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/872},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969440・969456・969461 に記録されました（2026年10月01日 19:28（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

部分和の問題は、表を作れば速く解ける、と言われる。本稿は、その表の大きさが数の個数ではなく数の大きさで決まることを、桁数を変えて数える。新しい定理も法則も主張しない。

第一に、表は数の大きさに比例する。$20$ 個の数で、$1$ 桁なら表は $1120$ ます、$3$ 桁なら $118980$ ますである（第2節）。

第二に、桁が増えると、表は全部の組を超える。$4$ 桁で表は全部の組 $2^{20}$ の $\mathbf{1.141605}$ 倍、$6$ 桁で $\mathbf{104.245529}$ 倍になる（第2節）。

第三に、これが本稿の芯である。桁を一つ足すと、表は掛け算で、入力の長さは足し算で増える。表は $\mathbf{9.277988}$ 倍から $\mathbf{11.053571}$ 倍になり、入力の長さは $62$ から $69$ ビット増えるだけである（第3節）。

第四に、だから表の手間は、入力の長さに対しては指数である。数の値に対しては多項式でも、値を書く長さは値の対数なので、長さで測ると桁ごとに十倍前後になる（第3節）。

第五に、表の答えは正しい。$12$ 個の数で $60$ 問、表で出した答えと、和を全部並べて出した答えが一致した（第2節）。

第六に、分離子は、入力の長さで測るか、数の値で測るかである。同じ表が、値で測れば多項式、長さで測れば指数に見える。これが擬多項式時間という呼び名の中身である（第4節）。

キーワード：部分和問題、動的計画法、擬多項式時間、入力の長さ、計算量

Abstract

Subset sum is said to be solved quickly by building a table.This paper counts, varying the number of digits, that the table’s size is set by the size of the numbers, not by how many there are.No new theorem or law is claimed.

First, the table is proportional to the size of the numbers: with $20$ numbers, the table has $1120$ cells for $1$ digit and $118980$ for $3$ digits (Section 2).

Second, with more digits, the table outgrows all subsets: at $4$ digits it is $\mathbf{1.141605}$ times all $2^{20}$ subsets, and at $6$ digits $\mathbf{104.245529}$ times (Section 2).

Third, and this is the core. Adding one digit multiplies the table but only adds to the input length: the table grows $\mathbf{9.277988}$ to $\mathbf{11.053571}$-fold while the input length grows by only $62$ to $69$ bits (Section 3).

Fourth, so the table’s work is exponential in the input length. It is polynomial in the values, but the length needed to write a value is its logarithm, so measured by length it grows roughly tenfold per digit (Section 3).

Fifth, the table’s answers are correct: on $60$ problems with $12$ numbers, answers from the table matched answers from listing all sums (Section 2).

Sixth, the separator is whether one measures by input length or by the values of the numbers: the same table looks polynomial by value and exponential by length; this is what the name pseudo-polynomial time means (Section 4).

Keywords: subset sum problem, dynamic programming, pseudo-polynomial time, input length, computational complexity

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/872/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/872 はいつも最新の版を指します）。

YOI の一覧へ