2026-09-20 · article P 対 NP回路計算量否定制限回路

P 対 NP — 否定の個数の梯子はどこで止まるか

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

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

答えを多項式時間で検算できる問題は、どれも多項式時間で解けるか。
（解けるなら P = NP。回路の言葉では、NP の関数のどれかに多項式サイズの回路が無いこと——NP ⊄ P/poly——を示せば P ≠ NP が従う）

ここで「回路」とは、AND・OR・NOT のゲートを配線して論理関数を計算する図式のことで、ゲートの個数をサイズと呼びます。P/poly は、多項式サイズの回路で計算できる関数の集まりです。難しさを示すとは、「この関数を計算する回路には少なくともこれだけのゲートが要る」という下界を証明することです。

過去の試みは、三つの障壁のどれかに当たって止まっています。障壁とは「この型の論法では P 対 NP を決められない」という定理で、次の三つが知られています。既知

• 相対化——計算機に「神託」（どんな問いにも一手で答える仮想の装置）を付けても、そのまま通る論法は使えない。
• 自然な証明——「ほとんどの関数が持ち、しかも効率よく判定できる性質」で難しさを示す論法は、強い擬似乱数生成器（計算では乱数と見分けがつかない列を作る仕組み）が存在するなら通らない。
• 代数化——神託を多項式に拡張したもの（低次拡大）を片側に与えても通る論法も、使えない。

進んだ道と、止まった場所：

ACC⁰・TC⁰ は深さが一定の回路の族（前者は剰余を数えるゲート、後者は多数決ゲートを許す）、NEXP・NQP は非決定性の指数時間・準多項式時間の類。perm（パーマネント）と det（行列式）は正方行列から作る二つの多項式で、パーマネントが大きさ多項式の行列式では表せないことを示すのが幾何学的複雑性理論の目標です。

三つの障壁を同時に避けている既存の技法は、実質 Williams の方法だけです。避け方は「対象を開ける」に尽きます——神託でなく回路の記述そのものに触り（非相対化・非代数化）、関数の集団でなく一点を扱う（large でない）。Williams 2013 は NEXP の下界について「構成性は不可避・large は不要」を同値として示しています。禁じられているのは、「多数の関数が持ち、かつ計算できる性質」を使うことです。NP について同じ同値が成り立つかは確認していません。

失敗した「証明」の多くは、この三つのどれかにそのまま当たります——神託を付けても通る、XORSAT・完全マッチング・Tardos 関数にも同じ結論が出てしまう、ランダム関数と擬似ランダム関数を見分けることになっている。P 対 NP の「証明」を集めた Woeginger の Web 上の一覧は 115 件（P = NP が 62・P ≠ NP が 50・決定不能が 3）。既知

単調回路（否定 0 個）には指数下界があり、一般回路には 3.1n しかありません。この二つの間を連続に繋ぐ数値が一つあります——回路が使ってよい否定ゲートの個数 t。t を一段ずつ増やしていく道を、この記事では「梯子」と呼びます。既知

• Markov の定理：f の計算に必要十分な否定の個数は I(f) = ⌈log₂(d(f) + 1)⌉。d(f) は、入力の増加鎖（入力のビットを一つずつ立てていく列）に沿って値が 1 → 0 と変わる回数の最大。したがって n 変数のどの関数も ⌈log₂(n + 1)⌉ 個で足りる。
• Fischer の定理：否定を ⌈log(n + 1)⌉ 個に絞る値段は、サイズ 2C + O(n² log² n)。つまり否定 ⌈log(n + 1)⌉ 個の回路に対する NP の関数の超多項式下界は、そのまま NP ⊄ P/poly。

以下で NC¹ は、深さが log n 程度で大きさが多項式の回路（多項式サイズの式と同じ力）で計算できる関数の類です。

NC¹ での到達を運んでいるのは Rossman の補題 1.3（Holley の単調結合）です。「1/2 + δ 困難」とは、その大きさのどの回路を使っても、入力を無作為に引いたときに正解する確率が 1/2 + δ に届かないことです。分布が FKG 束条件（正の相関を保証する条件）を満たし、単調関数 f がその下で均衡（値が半々に出る）なら、

否定 1 個の値段は、証明できる相関の余裕 δ が半分になることで、使える t の上限は t ≈ log₂(1/δ)。単調 NC¹ に対して取れる余裕は δ = n^−1/2+ε なので (1/2 − ε) log n で止まります。壊れるのは回路の構造の側ではなく、単調側の平均時下界の強さ（無作為な入力に対する正解率についての下界）の側です。同じ「否定 1 個＝2 倍」は、扱える交代数（Markov）・守れる独立なコピーの個数（Jukna）・サイズ（Fischer）にも現れます。

t を上げるだけでは足りません。P に属する明示的な単調多出力関数で、log n − O(log log n) 個以上の否定を許さなければ超多項式サイズが要るものが在ります（Jukna 定理 10.21）。一出力の明示的単調関数で同じことを求める問題（同 Research Problem 10.23）は未解決です。既知

以下、変数の個数を N と書きます（文献の引用では n のまま）。「測度」は入力の確率分布のことです。一様測度はすべての入力を等確率で引く分布、積測度は各変数を独立に引く分布、交換可能な測度は入力の重み |x|（真になっているビットの個数）だけで確率が決まる分布です。

天井 n^−1/2 は原理的である

どの単調関数も、0・1・x₁,…,x_n・MAJ（多数決関数）のどれかと 1/2 + Ω(log n/√n) で一致します（O'Donnell–Wimmer 2009）。これらはすべて単調 NC¹ に入るので、一様測度の下で、単調関数は単調 NC¹ に対して 1/2 + o(log n/√n) 困難になれません。Rossman 自身が論文の中でこの限界を述べ、積測度の下では多項式サイズの単調回路に対しても 1/2 + n^−1/2 より良い困難性は望めないと書いています。既知

1/2 の出所は一行で書けます。測度が交換可能（重み |x| だけで決まる）で f が均衡なら、φ(s) を重み s の層での f の密度として

紙・未検分閾値との相関は「φ が 1/2 から離れる速さ（傾き）× 重みが広がる層の数」。Kruskal–Katona の定理が傾きの下限 1/n〜log n/n を強い、一様測度の重みは √n 層に広がるので log n/√n です。1/2 は、積測度の下でハミング重み（重み |x|）が √N 個の層にしか住まないことから来ています。同じ √N は別の二箇所にも出ます：どの関数も否定 (1/2) log n + O(1) 個の回路で 0.01 近似できる（Blais–Canonne–Oliveira–Servedio–Tan）。擬似ランダム関数は否定 log n − O(1) 個を要するが、その証明は弱擬似ランダム関数には通らない——無作為な標本は中央の層に集中して鎖を張れない（Guo–Malkin–Oliveira–Rosen）。既知

積測度を替えても天井は下がりません：重みの分散を σ² とすると、どの積測度でも単調関数はある閾値と 1/2 + c/(σ√(log σ)) で一致し、この床——簡単な関数でも必ず取れてしまう一致の余裕の下限で、困難性はこれより先へ進めない——が最も低いのは、σ が最大の一様測度です（証明は既知の型）。紙・未検分FKG 束条件を満たす一般の測度については、証明が付いていません。

帯の補題と、梯子の上端

紙検分済み。帯とは、入力の重みをある範囲に限った部分のことです。重みが L 個の層から成る帯 a ≤ |x| ≤ b の上では、サイズ s の任意の回路を、否定 ⌈log₂L⌉ 個・サイズ 2s + poly(N)・深さ +O(log N) の回路に直せます。L = 1 が Berkowitz のスライス関数、L = N + 1 が Fischer の定理で、その間の補間です。証明は Fischer の構成を帯に制限しただけで、寸法つきの形は探した範囲に見当たりませんが、folklore（論文にはなっていないが専門家には知られている類の事実）と見るべきものです。

一様測度の帯 N/2 ± √N（L = 2√N + 1、帯の外の質量は 0.28 未満）に当てると：

明示的な f ∈ mSAC¹ が、否定 (1/2) log₂N + 2 個の NC¹ 回路に対して一様測度で 1/2 + 0.2 困難なら、f ∉ NC¹、すなわち NC¹ ≠ LOGCFL。紙検分済み

mSAC¹ は、LOGCFL（NC¹ を含み、それより大きいと信じられている類）の単調版です。NC¹ ≠ LOGCFL は P ≠ NP よりはるかに弱い分離ですが、これも未解決です。

定数の優位での言明で、1/poly の質を保つなら上端は (1/2) log N + (1/2) log log N + O(1) に上がります。Rossman の (1/2 − ε) log n は、最悪時の梯子（長さ log n）に対しては半分ですが、一様平均時の梯子に対しては上端まで ε log n + O(1) 段です。

技法の側の隙間 ε log n は、窓の幅 log log n よりずっと大きいままです。Fischer の構成は「⌈log(n + 1)⌉ 回の閾値質問でハミング重みを二分探索し、層が決まったら単調質問を一回」と読めます（否定 t 個の回路と深さ t + 1 の単調質問の決定木の対応は Amireddy–Jayasurya–Sarma 2023 の枠に入る既知。寸法の一致は本文未確認）。一様測度で (1/2) log n になるのは、探索範囲が √n 層だからです。自然な証明の障壁がこの梯子に掛かるのは最後の O(1) 段だけで、逆にスライス関数（L = 1）では全面的に掛かります。紙・未検分

Rossman の定理 1.1（k-CYCLE——有向グラフに長さ k の閉路があるかを判定する問題——は、臨界のランダムグラフ Γ の下で、小さな単調論理式に対して 1/2 + n^−1/2+c 困難）の証明を補題ごとに読むと、入力測度 Γ が積測度であることを使うのは、補題 C.4 の二本の式 (23)(24) だけです。どちらも Poisson 近似で、(24) は「Γ に道を一本植えても全変動距離（二つの分布の違いの大きさ）は O(k/√n)」。Janson の不等式と確率的優越は証明者が選ぶ雑音の側の独立性で、persistent minterm（minterm は関数の値を真にする極小の入力）の補題・パスセット複雑度の下界・否定への被覆（補題 F.2）は測度を含みません。Rossman の言葉では、雑音は “lives inside the variance of the random graph Γ”。既知 (23)(24) の証明は論文の完全版に回されていて、その所在は確認していません。

入力測度を「辺数が L 層の帯に入る」という条件つき測度に替えると：紙・未検分

• (24) が壊れる。道を植えると辺数が k − 1 増え、帯の上端の質量が外へ出るので、全変動距離は (k − 1)/L 以上。しかも単調な閾値で見つかる。Holley の単調結合にも同じ出所の欠損 1/L 以上が残る。障害物の名は「鎖の長さ」——単調な一歩は重みを動かし、L 層の帯の中の鎖は長さ L 以下。
• 黒箱の条件づけでも同じ値。基の測度で 1/2 + δ 困難なら、質量 q の帯の上での優位は 2δ/q 以下で、Rossman の値を入れると O(N^ε/L)。否定 t 個で o(1) に保てるのは t ≤ log₂L − ε log₂N − ω(1)。梯子の上端 ⌈log₂L⌉ との差 ε log N は L によらない——帯を狭めると上端と到達点が同じだけ下がる。
• 帯の上の床は「層の数 × 傾き」。(L − 1) log N/N の桁（log N の部分は概略）で、L = 1 では 0、L ≈ √N で log N/√N に戻る。tribes 関数で厳密に出した値は (L − 1)·傾き の 0.25・0.25・0.25・0.23 倍（n = 264・L = 3, 5, 9, 17）。計算
• 床と雑音の取引。重みが L 層に広がる交換可能な測度では、床が δ ≥ c·L·κ（κ は一層あたりの傾き）、技法が δ ≥ C·w/L（w は単調な雑音の重み）を要る。積は L によらず δ ≥ √(wκ) ≈ √(w/n)。交換可能な測度のどの幅でも n^−1/2 に戻り、Rossman の Γ はその最適点に居ます（この技法の内側での言明）。

帯を狭める道では、窓に入れません。補題 1.3 の損 2^t+1 − 1 は、単調質問が切る胞を無視して全体で和を取った損です。深さ j − 1 の単調質問の木の葉の胞ごとに、葉の単調回路が覆う単調対の質量を足した量を D_j とすると、否定 t 個の回路が覆う質量は Σ_{j ≤ t+1} D_j 以下で、自明な上界 D_j ≤ 2^j−1D₁ が補題 1.3 です。D_j ≤ K·D₁ が言えれば損は K(t + 1) に落ちます。紙・未検分質問を dictator（一変数だけを見る関数）に限り f = MAJ_N とした玩具では D₂/D₁ = 0.583, 0.633, 0.668, 0.766, 0.884, 0.961（N = 5, 7, 9, 21, 101, 1001。自明な上界は 2）。計算一般の単調回路の質問についてこれを示す道具はありません。

取引から抜ける道は、交換可能でない測度で傾きを 0 にすることです。Rossman の入力は k 個の頂点クラス（各 n 頂点）を巡回する有向グラフで、変数は N = kn² 本の辺、Γ は各辺を確率 p ∼ (ln 2)^1/k/n で入れる積測度。Γ₀ を「k 閉路なし」で条件づけた Γ、⊙ を一様な k 閉路とします。

重み中立の植え込み——床の名前は「道の数」

「植え込み」とは、無作為なグラフに閉路などの構造をわざと入れることです。判定させたい問いは「閉路が植えてあるか」で、1 側・0 側はその答えが 1・0 になるべき入力の分布です。1 側を Γ₀ ∪ ⊙、0 側を Γ₀ ∪（各辺クラスから一様に 1 本ずつの k 辺）とすると、両側の辺数の分布が一致し、辺数の閾値・単一の辺・入次数だけ／出次数だけの関数は優位が 0 になります。それでも床は落ちません。j 辺の有向道の数 P_j の閾値が、c = pn として

の優位を取ります。k = 4 のとき P₂ で 0.101·√(k/n)、j = k − 1・c → 1 で約 0.17·k/√n。紙・未検分標本では P₂ の優位 × √(n/k) が 0.097・0.104・0.094・0.098（k = 4、n = 30, 60, 100, 200）で、式と 8% 以内で合います。計算これは (24) の右辺 O(k/√n) が桁として等号であることの言い換えで、Γ の下でも既に同じ統計量が床でした。測度を中立にしても、証明の側が「底」と「底に道を植えたもの」を比べる——閉路が minterm であることを言うための比較——ところで重みを動かします。

閉路の 2-被覆の植え込み

0 側の植え込みも同じ局所構造にします。各クラスから 2 頂点ずつ選び、辺クラスごとに K_2,2 の二つの完全マッチング（平行か交差か）のどちらかを植える。交差の個数が偶数なら k 閉路 2 本（1 側）、奇数なら 2k 閉路 1 本（0 側）で、全頂点の（入, 出）次数まで一致します。側は k 個の辺クラスに一つずつ隠れたねじれビットのパリティです。紙・未検分

• 辺クラスを一つでも見ない関数の優位は、厳密に 0（単調でなくても）。
• d < k 辺の道の数の閾値の優位は O(poly(k)·n^{−⌈k/d⌉/2})（概略）。標本では (n, k) = (30, 4)・200,145 対で P₂ の優位は −0.00007 ± 0.00010。計算
• 端点の異なる k 辺の道の数は、0 側に −Θ(√(k/n)) で相関する（単調だが反対向き）。標本で −0.0310 ± 0.0003（n = 30）、n = 30 → 60 の比 0.76（√(1/2) = 0.71）。計算

片側の床は n^−1/2 より下に落ち、両側（絶対値）の床は残ります。ただし残る統計量は n^k+1 項で、k → ∞ のとき多項式サイズの単調論理式に入るかは分かっていません。計算の陰性対照（差が出ないはずの対で同じ測定をする対照実験。ここでは同種を独立な位置に植えた対）に、大きさ 10⁻³・約 2.6σ の未解明のずれが一つあり、「0」の解像度は 10⁻³ と読むべきです。

交代和の補題——否定への拡張に Holley は要らない

重み中立の測度では両側に比較可能な対が無く、単調結合は存在しません。それでも：

任意の二つの分布について、否定 t 個・サイズ s の回路の優位は 2^t+1·δ₂ 以下。δ₂ は、サイズ (2t + 1)s 以下の単調回路が取れる優位の絶対値の最大（両側の単調困難性）。紙・未検分

系：f ∈ NC¹ なら否定 ⌈log₂(N + 1)⌉ 個の回路が f を厳密に計算するので、ある分布の対の下で δ₂ < 1/(8(N + 1)) が言えれば f ∉ NC¹。積測度の下では §03 の天井がこの線を原理的に塞ぎます。2-被覆の測度の下では、見つかった単純な統計量はこの線を妨げません（d < k/4）。つまりその床を証明として下げることは、NC¹ ≠ NL と同じ重さ（NL は対数領域の非決定性計算の類で、NC¹ を含む）を持ちます——床が落ちることと、落ちた床まで証明が届くことは別です。Rossman の証明を黒箱で使うと、2-被覆の測度の下でも否定 (1/2 − c) log n 個まで（同じ値）。その先を阻むのは、補題 4.5 が和集合の上界で加法的に払う (ℓ + 1)k²/√n です。小さいのは符号つきの差だけで、相殺を使う証明が要りますが、minterm の数え上げは符号を持ちません。

辺数の期待値を合わせた帰無仮説は Addario-Berry–Angel–Lugosi–Rácz–Schramm にあります。次数列まで合わせた植え込みを単調回路について論じたもの、交代和の補題の明示形は探した範囲に見当たりませんが、後者は folklore の範囲の一行です。

模型：入力は x₁,…,x₄ のみ（定数入力なし）。ゲートは二項の AND・OR と一項の NOT で、サイズは AND/OR の個数（NOT は数えない）。C_t(f) は NOT を t 個以下しか使わない回路の最小サイズ、C_∞ は否定が無制限のときの値、C₀ は単調回路。全 65,536 関数を、正準形の回路の全列挙で数えます。

否定の値段が立つのは、一箇所だけ

n = 4 では単調性の値段がゼロで、否定を 3 個から 2 個に絞る値段もゼロです。値段が立つのは、どの関数にも足りる個数（Markov の定理から 2 個）を割って 1 個に絞ったときだけ。最大の 4 ゲートを取るのは対称関数ではなく多重化器で、否定の使い道が二つとも本質的（選択信号の中に一つ、選択そのものに一つ）です。比 8/4 = 2 は Fischer の係数と同じ数ですが、一般には乗算的ではなく加法的です：アドレス k ビットの多重化器は d = k・I = ⌈log₂(k + 1)⌉ で、t ≥ I なら C_t ≤ C_∞ + O(k log k)。紙・未検分選択信号が単調なら n = 4 でも値段は 0 です（x₃ ? x₂ : x₁ は C₁ = C₂ = 3）。この形は n = 4 の小ささに固有で、漸近的には t = 0 の単調関数で既に指数の値段が立ちます。

対称関数の側は、否定の入力が閾値関数に一意に固定される剛性（Tanaka–Nishino–Beals）で説明がつきます。E₁（ちょうど 1 個）の C₁ = 9 は、固定された入力 T₂ の C₀ = 7 を丸ごと背負った値です。計算

否定 1 個の回路は、単調な塊の和に分解しない

否定 1 個の回路は f = M(x, ¬h(x))（h, M は単調）と書けます。h の単調回路と、¬h を自由な入力に持つ単調回路を別々に最適化した和が D₁ です。D₁ = C₁ がいつも成り立つなら、単調側の指数下界が t 段ぶんの損失だけで否定制限回路に乗り移ります。n = 4 で既に成り立ちません。

得の源は単調多出力回路の共有で、否定に固有ではありません。観測された差の最大 6 と γ の最大 6 は同じ対 (T₂, T₃) で起きていて、不等式は最大値のところでちょうど達成されます。Fischer の定理の証明自体が、n 個の閾値関数を一本の単調回路でまとめて作る共有の構成で、E₂ はその n = 4 版です。多重化器では差が 0 なので、「否定の値段」と「共有の得」は別の現象です。否定制限のサイズが単調な塊のサイズの和に分解する、という言明は Jukna の第 10 章を探した範囲に見当たりません。梯子を「分解」で登る道は、多出力単調下界という別の未解決問題に置き換わります。

対照：否定制限の列挙は六本（単調関数 166 個の再現・Markov の下界側の違反ゼロ・t = 3 の表が t = 2 と全升一致・刈り込み無しの列挙との一致・独立な表に対する C_t ≥ C_∞・剛性定理）。C₂ が厳密なのは 65,536 中 61,184（93.4%）、C₁ は否定 1 個で作れる 23,760 中 20,252（85.2%）で、残りは下界だけ。D₁ は 23,760 関数すべてで厳密（対照は八本）。別実装による C₁ の再現は C₁ ≤ 6 の 100 関数で 100/100 一致、C₁ が 7〜9 の升は再現していません。

n = 4 の全数計算は、障壁に触れません。真理値表を持てば何でも 2^O(n) 時間で判定できるので「構成的」の条件が空で、しかも n = 4 では対称関数のような明示的な族が全体の最大値に達していて、ほとんどすべての関数の難しさと明示的な一点の難しさがまだ分離していません（Knuth も、対称関数は n が小さいとき最も評価しにくく n ≥ 10 では最も易しい部類になる、と書いています既知）。

非可換の設定（Nisan の代数的分岐プログラム）では最小サイズが階数で厳密に書けますが、n ≤ 8 の全数で perm と det の階数は完全に一致します（どちらも二項係数）。計算差が出るのは安定化群のリー環の次元（安定化群はその多項式を変えない線形変換の集まり、リー環の次元はその連続なパラメータの個数）です：

幾何学的複雑性理論が実際に扱うのはパディングした ℓ^m−nperm_n ですが、パディングが増やす対称性はちょうど 1 次元（ℓ と x の同時スケーリング）で、行列式側も同じく 2n² − 1（n = 2, 3, 4 で 7・17・31）。連続な対称性の差は、n について一次と二次のまま残ります。ただし、これは障害には翻訳できません。安定化群が小さいこと自体は軌道閉包への包含を妨げず（境界では安定化群は逆に大きくなりうる）、§01 のとおり occurrence obstruction の道は閉じています。「2n − 1 で m に依らない」という逐語の言明は探した範囲に見当たりませんが、初等的な計算で、専門家には自明でありえます。

動いた宿題の現在地は 残っていること にある。ここには現時点の未決だけを置く。

式サイズの側（De Morgan 式サイズを、真理値表の上の関数として見る）は 別のページ にあります。

• 窓（幅 log log N）に入る道具が無い。補題 1.3 は天井のために入れず、帯を狭める道は鎖の長さで閉じ、交換可能な測度は n^−1/2 に戻る。
• 多出力単調下界。梯子を分解で登るのに要るのは、組 (h, g⃗) の多出力単調複雑さの下界。一出力の明示的単調関数についての Jukna の Research Problem 10.23 も未解決。
• 2-被覆の測度の下での、補題 4.5 の乗法版。加法的な損 (ℓ + 1)k²/√n を条件つきの形に替えられるか。反例探しから始めるべき問いで、着手していない。
• t = 2 の全数（二段の分解 D₂ 対 C₂）は未着手。見積もりは 90 時間。
• n = 4 の表の空き：C₁ ≥ 10 のまま値が未定の 3,508 関数、C₂ ≥ 9 のまま未定の 4,352 関数、0x1886 の上界、γ の 6 対。関数ごとの等号 D₁ − C₁ = γ は測っていない。
• 紙の側の空き：一般の FKG 測度での天井、2-被覆の下での道の数の優位（概略）、端点の異なる k 辺の道の数が k → ∞ で単調 NC¹ に入るか、植え込み測度の下で Rossman の証明が通ること（概略）。
• 計算の陰性対照に残る約 2.6σ（大きさ 10⁻³）のずれの原因。
• † を付けた文献の原典、Amano–Maruoka 2005 の本文、Rossman の論文の完全版（(23)(24) の証明）の確認。

このページの主張に、機械検査されたものはありません。紙の補題のうち読み直しを経たのは帯の補題とその系だけで、探した範囲に見当たらないと書いたものも、どれも folklore の範囲の短い議論です。この筋は、ここで止めてあります。

文献

探した範囲：arXiv の検索（negation-limited circuits・monotone circuits average-case・slice functions monotone circuit・pathset complexity・planted cycle detection ほか）。被引用の一覧は引いていません。