Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

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

本文はサイトの記事でも読めます：【論文4】総当たり探索の物理的資源限界

@misc{yamagishi2026yoi4,
  author = {Yamagishi, Yuuki},
  title = {The Physical Resource Bound on Brute-Force Search},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/4},
  doi = {10.5281/zenodo.21404131},
  note = {Preprint, edition 3}
}

日付の証拠（OpenTimestamps）

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

書誌

要旨

$2^n$ 個の候補を実際に走査する総当たり探索には、ランダウアーの原理による下限が存在する。本稿はその下限を正確に述べ、そこから何が言えて何が言えないかを書き分ける。第一に、定理の正確な形は「非可逆な操作について」である。 ランダウアー限界は1ビットの消去あたり $k_BT\ln2$ の仕事を要求する。他方ベネット（1973）は可逆計算が原理的に散逸をいくらでも小さくできることを示した。したがって下限が拘束するのは非可逆な実装であって、探索そのものではない。 この限定は本質的である。第二に、そしてこれが第3版の主眼である。ロバストな言明は線形ではなく対数のほうである。 第2版は $n=300$ における必要エネルギーを「観測可能宇宙の質量エネルギーの約0.6倍」と記していた。だがこの比は、宇宙の質量をどう見積もるかで 0.43 から 1.08 まで動く。「約0.6倍」は精度の偽装である（論文101）。これに対し、必要エネルギーが利用可能エネルギーに達する $n^*$ は動かない。$n^*=\log_2\!\big(E/(k_BT\ln2)\big)$ であるから、エネルギーの見積りを $2.5$ 倍動かしても $n^*$ は $1.3$ しか動かず、温度を $300$ K から $2.7$ K へ $111$ 倍下げても $6.8$ しか動かない。言うべきは「約0.6倍」ではなく「$n\approx300$」である。 第三に、これはモジュールの境界である。 無次元比 $E_{\text{必要}}/E_{\text{利用可能}}$ が $1$ をまたぐ場所であり、論文39のプランク尺度、論文09の $\Lambda\lesssim4\pi v$、論文03の $\mathrm{Re}_\eta=1$ と同じ構造をもつ。ただしこれは物理的実装の境界であって、計算量クラスの境界ではない。 第四に、消去は粗視化である。 論理的非可逆性とは二つの状態が一つに落ちることであり、ミクロな力学が可逆（リウヴィル、論文77）である以上、その分は環境へ渡さねばならない（論文78）。ランダウアー限界は、情報と熱力学を結ぶ定量的な橋であり、実験的にも検証されている（Bérut ら 2012）。第五に、三つの障壁は計算量理論版の「機械の移送テスト」である。 相対化・自然証明・代数化は、どの種類の道具がこの問題に効かないかを述べる定理であり、論文100の移送テストと同型の役割をもつ。本稿はそのいずれにも答えない。 射程：既存の物理法則・定理の構造的整理（第2層）。$\mathcal{P}$ vs $\mathcal{NP}$ はクレイ数学研究所のミレニアム懸賞問題であり未解決である。本稿はその証明も部分的証明も、証明への道筋の提示も主張しない。

Abstract

A brute-force search that actually scans $2^n$ candidates is bounded below by Landauer’s principle. This paper states that bound precisely and writes out what does and does not follow from it. First, the exact form of the theorem is “for irreversible operations”. Landauer’s limit demands $k_BT\ln2$ of work per bit erased. Bennett (1973), by contrast, showed that logically reversible computation can in principle dissipate arbitrarily little. The bound therefore constrains irreversible implementations, not search itself. That qualification is essential. Second（and this is the point of the 3rd edition）the robust statement is the logarithmic one, not the linear one. The second edition described the energy required at $n=300$ as “about $0.6$ times the mass-energy of the observable universe”. But that ratio ranges from $0.43$ to $1.08$ depending on how the mass of the universe is estimated. “About $0.6$ times” asserts a precision it does not possess (Paper 101). By contrast, the $n^*$ at which the required energy reaches the available energy barely moves. Since $n^*=\log_2\!\big(E/(k_BT\ln2)\big)$, changing the energy estimate by a factor of $2.5$ moves $n^*$ by only $1.3$, and lowering the temperature from $300$ K to $2.7$ K、a factor of $111$、moves it by only $6.8$. What should be said is not “about $0.6$ times” but “$n\approx300$”. Third, this is a module boundary. It is the place where the dimensionless ratio $E_{\text{required}}/E_{\text{available}}$ crosses one, structurally the same as the Planck scale of Paper 39, the bound $\Lambda\lesssim4\pi v$ of Paper 09 and the $\mathrm{Re}_\eta=1$ of Paper 03. But it is a boundary of physical implementation, not of complexity classes. Fourth, erasure is coarse-graining. Logical irreversibility means two states collapsing into one, and since the microscopic dynamics is reversible (Liouville, Paper 77), the difference must be passed to the environment (Paper 78). Landauer’s principle is a quantitative bridge between information and thermodynamics, and has been verified experimentally (Bérut et al. 2012). Fifth, the three barriers are complexity theory’s version of the machinery-transfer test. Relativization, natural proofs and algebrization are theorems about which kinds of tool cannot reach this problem, playing the same role as the transfer test of Paper 100. This paper answers none of them. Scope: a structural account of established physical law and theorems (Layer 2). $\mathcal{P}$ vs $\mathcal{NP}$ is a Clay Millennium Prize Problem and is unsolved. This paper claims neither its proof, nor a partial proof, nor a route towards one.

版の記録

ここの PDF（倉庫の v1）は第3版（2026年8月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/4/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/4 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。

YOI の一覧へ