2026-09-20 · article P 対 NP回路計算量式サイズ

式サイズを、真理値表の上の関数として見る

主張ごとに、確からしさの等級を次の札で示します。

Lean機械検査済み——このページには一つもありません 紙証明はあるが機械検査は未了。別の機会に証明を読み直して壊れなかったものには「検分済み」と添える 紙・未検分証明は書いてあるが、読み直しを経ていない 計算この端末で確かめた範囲。外に出す主張にはしない 既知既知の定理・外の文献の確認。† は原典を取得せず標準的事実として引いたもの

真理値表とは、関数の値をすべての入力について並べた表のことです。n = 4 では入力が 16 通りなので真理値表は 16 ビットの列で、関数は全部で 65,536 個あります。その全部について L を厳密に計算した表が取れるので、難しさそのものを真理値表 {0,1}¹⁶ の上の一つの関数として扱えます——L を、16 ビットの列を受け取って数を返す関数として調べる、ということです。

表に出る用語：全影響 I(P)（全感度とも）は、入力の一つのビットを反転したとき値が変わる確率を全ビットで足したもの。Fourier 重みは、関数をパリティ関数（幾つかの変数の XOR）の和に分解したときの各成分の大きさで、次数はそのパリティに含まれる変数の個数。乱択集合は、同じ密度で無作為に選んだ集合。Khrapchenko の下界は、f が 1 になる入力の集合 A と 0 になる集合 B の間の辺（一つのビットだけ違う対）の数 |E| から L ≥ |E|²/(|A||B|) を出す古典的な式。線形計画は、一次の不等式を制約にして一次の目的関数を最適化する問題。

L は真理値表の 1 ビット反転で高々 n しか動きません（リプシッツ性——入力を少し変えても出力が少ししか動かない性質）。紙・未検分だから難しさの性質 P_s = {L ≥ s} の全影響は同密度の乱択集合の約半分になり、s について足し上げると恒等式になります。重みは低次に集中し、指しているのは Khrapchenko の下界が使っている量（全感度）です。フーリエの側では Khrapchenko の量は一行で書けて、一様測度なら全影響の二乗そのものです：

リプシッツ性は初等的で既知でありえ、恒等式は層別公式（値を閾値 s ごとに切って足し上げる恒等式）の一行です。

Khrapchenko が数えるのは 1 と 0 を隔てる辺です。数える単位を 2 次元の面（部分立方体——幾つかの変数を固定し、残りを自由に動かした入力の集まり。n = 4 では 24 枚、一般に C(n, 2)2ⁿ⁻² 枚）に上げ、面の上の制限（f をその面に限った関数）を型で分けて数えます——一つの隅だけが他と違う面の枚数 N₁（制限が AND 型・OR 型）、1 が辺で隣り合う面の枚数 N_隣（制限が一変数）、1 が対角にある面の枚数 N_対角（制限が XOR）。この三つ組は L を保つ群（入力の反転・変数の入れ替え・出力の反転という、L を変えない変換の集まり）で不変なので、下界の材料としての資格があります。

L を三つ組の一次式で近似する回帰の説明率は、辺だけの 76% から 93% に上がり、最も重いのは制限が XOR になる面の枚数です。ただし回帰は下界ではありません。この式をそのまま下界として使うと、半分の関数で破れます。下界として証明できる形は、全数を拘束にした線形計画で厳密に決まります：

n = 4 は全数なので、これは 65,536 個すべてについての有限の検証で、整数演算だけで確かめられます。計算等号を与える 334 個の関数が係数を一つずつ釘づけにしていて、N_隣 の 1/12 は文字 x₁（φ = (0, 12, 0)・L = 1）、N₁ の 1/3 は x₁x₂ ∨ x₃x₄（φ = (10, 8, 0)・L = 4）、N_対角 の 2/3 は XOR₄（φ = (0, 0, 24)・L = 16 なので 16/24）が決めます。回帰の係数 0.8988 は 2/3 の 1.35 倍で、大きすぎて下界になりません——これが回帰が半分で破れる理由です。この陽な不等式と、それが n = 4 で Khrapchenko を一つの関数も下回らずに上回るという測定は探した範囲に見当たりませんが、複雑さ尺度の下界を線形計画で最適化する枠組みそのものは標準的です。

同じ形を n = 5 に持つと、係数は文字 x₁ 一つで破れます。方向 1 を含む面はすべて「隣」で N_隣 = (n − 1)2ⁿ⁻² なので、n = 4 では 12 でちょうど等号、n = 5 では 32 に対し左辺は 12 のままです。紙・未検分係数は面の枚数（24 → 80）に貼りついていました。枚数で割った密度の形に直せば、厳密な L が言える側——葉数 7 以下の n = 5 関数 662,176 個——の上では破れません。ただしこの隅だけで線形計画を解くと、係数は N_隣 の符号まで n = 4 の答えと食い違い、L を並べ替えた陰性対照（本物の L の代わりに値を混ぜ替えた L で同じ手続きを走らせ、何も出ないはずの対照実験）とほとんど同じ形（定数項と小さな係数）を返します。易しい側だけを見ている限り、線形計画は「L ≥ 定数」しか言っていません。計算

面の型を水準 k の部分立方体の型に一般化すると、この種の下界はすべて線形計画に収まります。型 T（変数の入れ替えで移り合う k 変数関数をひとまとめにしたもの）について ν_T(f) を「k 次元部分立方体のうち制限の型が T のものの割合」とすると、L(f) ≥ Σ_T c_Tν_T(f) の形のうち g について最も強いものの値は、線形計画の双対（同じ最適値を持つ裏側の問題）で

紙・未検分すなわち g の型プロファイルを再現する最も安い混合の L コストです。局所統計（大きさ k の部分立方体への制限の型の頻度）だけを拘束に使う線形計画の階層の、水準 k にあたる形です。強さがここで決まるので、g の下界を大きく証明するにはg のプロファイルを共有する易しい関数が居ないことが要ります。

2 面が全部「対角」になる関数は XOR_n とその否定のちょうど 2 個です（すべての二階差分が 0 ⟺ 二元体 F₂ 上の多項式としての次数 ≤ 1、台が全変数なら XOR_n）。プロファイルを共有する相手が自分の否定しか無いので、水準 2 だけで V₂(XOR_n) = L(XOR_n) が厳密に出ます。紙・未検分その値が n² になるのは n が 2 の冪のときだけで、L(XOR₃) = 10 に対し Khrapchenko の 9 は 1 だけ届きません。計算既知n = 4 の全数で解くと、水準 2（型 6・面 24 枚）は 328 プロファイルのうち 113 で L を厳密に決め、水準 3（型 22・8 枚）は 400 のうち 324 で決めます。水準を上げると厳密に強くなります。計算壁は一次形の天井ではなくプロファイルの衝突で、水準 k の型の個数は 2^2k/(2^kk!) の桁（概略）なので、k = O(1) の局所統計では関数を区別しきれません。

Khrapchenko の量を別の評価器で測っても天井は動きません。|E| ≤ n·min(|A|, |B|) から Kh ≤ n²、二部隣接行列（A と B の間の辺を並べた行列 M）のスペクトル（最大特異値 σ_max）で測る Koutsoupias 型 L ≥ σ_max(M)²既知も σ_max(M) ≤ n から Ko ≤ n² で、部分集合を選ぶ自由を入れても同じです。紙・未検分しかも等号は M が両側 n-正則であることを要求し、立方体が連結なので彩色が全体に伝播して f はパリティに決まります——天井に達するのは XOR_n とその否定だけ。n = 4 で最も難しい 114 関数のうち、この族が真値 16 を証明できるのは 2 個で、残りは 15・14・12 までです。値としては Ko のほうが L に近いのに L との相関は下がります。相関は尺度不変なので、これは定数倍の差ではなく、スペクトルに上げると L と無関係な方向の情報も拾っているということです。計算

評価器を一つずつ試す代わりに、ある不変量から原理的に引ける最良の下界を測ることもできます。不変量をフーリエの重みプロファイル W(f) = (W₀, …, W_n) に取れば、そこから引ける最良は B(f) = min{L(g) : W(g) = W(f)} です。n = 4 では相異なるプロファイルが 144 通り（入力の反転・変数の入れ替え・出力の反転で移り合う関数をまとめた NPN 同値類 222 個既知より粗い）しか無いのに、天井は 16 = max L に届き、届くのは XOR の 2 個ではなく L = 16 の 114 関数の全部です。最難の 114 個はちょうど 4 つのプロファイルに入り、その 4 類に易しい関数は一つも混ざりません。混線するのは易しい側で、最大の損 6 は重みが全部 2 次に乗るプロファイル——L = 4 の x_i ⊕ x_j と L = 10 の関数が同居する類——に出ます。計算不変量を全影響と密度の二数だけに落とすと、天井に届くのは XOR の 2 個に戻ります。

ただし B は L の厳密表を神託（答えをただ教えてくれる装置）として使って定義した量で、使える証明法ではありません。測っているのはプロファイルが持つ情報量——「重みだけを見て最難関数を取り違えない余地が n = 4 では残っている」——までです。n = 5 では L の全数（2³² 関数）が取れないので同じ測定はできず、厳密な L が言えるのは葉数の小さい隅だけです。ここに並んだ数はどれも n = 4 と n = 5 のその隅に閉じていて、障壁には触れません（一本目の三つの障壁のどれにも掛からない代わりに、そこから先へも進めない）。

そして、方法族を替えても水準を上げても、天井に届く関数は同じ一点です。辺の数え上げ、そのスペクトル版、型の密度の線形計画の水準 2 は、どれも XOR_n の n² を厳密に出し、それ以外の最も難しい関数では真値に届きません。「最も難しい関数」と「難しさを証明できる関数」は、ほとんど重なっていません。

• 型の密度の線形計画が n ≥ 5 でどれだけ強いか。n = 4 の全数で解いた水準 2・3 を、厳密な L が言える n = 5 の側（葉数 7 以下の 662,176 関数）に持っていっていない。水準 3 の陰性対照（L を並べ替えて同じ線形計画を解く）も未実施。
• プロファイルの衝突の定量。水準 k の型の個数と関数の個数の数え上げ（k = O(1) では関数を区別しきれないこと）を定量化していない。φ だけで言える下界の緩み 0.571 が n とともにどう増えるかも測っていない。
• 面と評価器の空き：等号を与える 334 個の群の軌道としての分類、L(XOR₅) の厳密値（Khrapchenko の 25 以上で、構成の上界も測っていない）、スペクトル版の相関が Khrapchenko より低い理由（どの方向の情報が混ざるのか）。フーリエ重みプロファイルの測定は、L の厳密な全数表が無い n = 5 へは伸びない。

このページの主張に、機械検査されたものはありません。

文献