P vs NP を追いかける

最初に、現在地を一枚に

初めて読む方は第1〜5章から。補題を検証する方は第7〜11章へ。証明の詳細は折りたたみを開けます。数式と図はオフラインでも読め、操作例と再現用ファイルもこのHTML内に含まれています。

答えの候補を確かめるのが速い問題は、答えの有無を決めるのも速いのでしょうか。

ここでの「速い」は、入力の長さに対する多項式時間です。長さを m とすると、ある固定定数 c について O(m^c) 時間で終わることを指します。特定の小さな入力で数秒だった、という意味ではありません。

NP は「多項式時間では解けない問題」の略ではありません。P ⊆ NP は分かっています。残る問いが、P=NP なのか P≠NP なのかです。Clay Mathematics Institute も、この問題を未解決のミレニアム懸賞問題として掲載しています。[1]

具体例：SAT と 3-SAT

SAT は、0 / 1 の変数からなる論理式を、全体が 1 になるようにできるかを尋ねます。∧ は AND（両方が1）、∨ は OR（少なくとも一方が1）、¬ は NOT（0と1の反転）です。CNF は OR のまとまりを AND で結んだ式。本ページで 3-CNF は、一つの OR のまとまりに高々3個のリテラルがある式を指します。

たとえば a=1、b=1、c=0 を代入すると、三つの節すべてが 1 です。この割当てが証人です。式の長さに比例する程度の処理で確認できます。SAT は NP 完全なので、SAT に一様な多項式時間アルゴリズムがあれば P=NP です。

最初の発想は、探索の重複を意味によって取り除くことでした。変数の一部を決めたとき、残りの変数に対して同じ振舞いをするなら、そこまでの履歴を区別する必要はないかもしれません。

関数 f の先頭 i 個の変数に割当て α を代入した関数を、残余関数 f_α と呼びます。二つの履歴 α、β が合流できる条件は、残りのすべての割当て z について f_α(z)=f_β(z) となることです。

OBDD：読む順番を固定した分岐図

この発想は OBDD（Ordered Binary Decision Diagram）と深く関係します。OBDD は、変数を固定順序で調べ、各変数を一つの経路で高々一回読み、最後に 0 / 1 へ到達する図です。同じ残余関数を共有すれば、枝を合流できます。

「まだ解がある」という一ビットでは、未来を区別できない

残りの関数が z の場合も ¬z の場合も、いまは解があります。しかし次に z=0 を読むと、一方は不充足、他方は充足です。「解あり」という一ビットだけでは、この更新を正確には行えません。

ただし、これは「一ビットの存在情報だけから更新する」という方式への反例です。一般の SAT アルゴリズムの不可能性を示したものではありません。

特定の分岐図に対する下界を、あらゆる計算の下界へ移すには、別の定理が必要です。

HWB（Hidden Weighted Bit）は、入力中の 1 の個数を w と数え、その番号の入力ビットを返す関数です。通常の添字 x₁,…,x_n を使い、w=0 のときは 0 と定義します。数えて一箇所を読むので、多項式時間で評価できます。一方、すべての変数順序で OBDD が指数的に大きくなることが知られています。[2]

さらに、変数の否定を含まない単調な 2-CNF には、OBDD の指数下界を持つ族があります。それでも SAT の答え自体は、全変数に 1 を入れれば YES です。[3] これらは、特定形式で全体を表す難しさと、入力に答える計算の難しさが一致しない具体例です。

研究上の訂正：条件文を「反証済み」にしない

以前の検討には、次の橋がありました。「もし SAT∈P なら、全 3-CNF の全解集合に多項式サイズの OBDD がある」。この扱いには、重要な論理上の訂正が必要でした。

反証できたのは「P で評価できるすべての関数には、小さい OBDD がある」という一般原理です。SAT∈P を前提とする上の条件文を、無条件に偽と判定したわけではありません。

正規形を使う計画に残る負担

研究の中では、一般の計算を共通の表現へ変換し、そこで下界を示す CCP・E-NF という案も検討しました。ただし、表現を弱く制限すると HWB のような簡単な関数を小さく表せません。十分に強くすると、今度はその形式への下界自体が一般回路下界に近づきます。

変換器の時間、途中で生じる表現の大きさ、変数を消す操作、更新後の正規化まで数える必要があります。小さい最終表現が存在するだけで、これらの作業が無料になるわけではありません。知識コンパイルの先行研究は、表現形式ごとに可能な問い合わせと変換を整理しています。[4]

次に調べる対象は、MCSP（Minimum Circuit Size Problem）です。n 変数関数の真理値表そのものと回路サイズの閾値 s を受け取り、「この表を計算する、サイズ s 以下の回路があるか」を問います。

x_j は整数 j の n ビット表現です。本ページでは 00…0、00…1、…、11…1 の順に並べます。n=2 なら 00、01、10、11。OR の表は 0111 です。

回路の数を数えると、状態数だけの案は止まる

回路は、入力を AND、OR、NOT のゲートで結んだ DAG（閉路のない有向グラフ）です。計算した途中の値は何度使っても構いません。n≤s とすると、サイズ s の回路は、各ゲートの種類と接続先を O(s log(s+2)) ビットで記述できます。したがって、そのような回路が表せる異なる真理値表の数 M は、

です。回路が異なっても同じ関数を計算する場合があるので、これは上界です。

この上界によって、残余状態数の爆発だけで poly(s) を超える空間下界を出す MREC という予想は反証されました。状態の短い名前が存在することは、次の名前を速く計算できることとは別です。そこで、焦点を状態数から更新計算へ移しました。

表をまだ途中までしか読んでいなくても、読んだ部分を説明する小さな回路を、いつでも取り出せる仕組みを考えます。

長さ i の出力 prefix を u=u₀…u_i−1 とします。u を説明できる小さな回路の集合を、次で定義します。

V は候補の集合であって、実装がその全要素を列挙して持つ必要はありません。また、未読の出力をすべて決めた小回路 C を、u の completion（補完回路）と呼びます。

live-promise WC は、live のときだけ正しい証人を求める緩い仕様です。ただし、dead でどの停止・資源条件を課すのかは、別に指定しなければなりません。還元に使うとき、この違いが重要になります。

McKay・Murray・Williams（MMW, 2019）は、資源制約付きの圧縮の下界を、強い複雑性クラスの分離へ結びつけました。ここでは原論文の Circuit-Min-Merge の構成を、一ビットごとの証人保持へ適用します。[5]

なぜ、過去を保存せずに更新できるのか

現在の小回路 C_i が過去の値をすべて再現しているなら、新しい候補 D は、過去の各位置で C_i と一致すればよいのです。長大な prefix の代わりに、小さい C_i を比較対象にします。

この「候補 D が存在し、すべての過去の位置で条件を満たす」という論理は、多項式階層 PH の中で表せます。P=NP なら PH は P に潰れるので、その探索を一様な poly(s) 時間で行えます。

回路サイズに十分な余裕があれば、「次の値は絶対に0」「絶対に1」という強制は崩せます。

長さ i の prefix u に整合する回路 C を一つ持っているとします。次に読むのは位置 i。過去の値を一切変えず、その位置の出力だけは好きな値にできるでしょうか。未読の他の値は変わってよいものとします。

証明の中心は「1 の位置を含めば、整数として小さくならない」

a_i(z)=1 なら、i の 1 ビットは z の中にもすべてあります。残りの桁に 1 が追加されることはあっても、i にある 1 が消えることはありません。各桁の重みは正なので、整数として z≥i です。

従って、過去の位置 j<i では a_i(x_j)=0、ちょうど位置 i では 1 です。C∨a_i は過去を変えず次値を 1 にし、C∧¬a_i は過去を変えず次値を 0 にします。

どんなときに、次の値を強制できるのか

u に整合する回路の最小サイズを τ(u) とし、閾値までの余裕を s−τ(u) とします。ここで「次が b に強制される」とは、V_n,s(u) 内のすべての回路で次の値が b になることです。

理由は、余裕があれば反対の値へ変更できてしまうからです。特に s−τ(u)≥w+1 なら、次の 0 / 1 の両方が可能です。

次は、連続する k 個の出力を好きな値へ変更し、その区間の外では元の回路をすべて保存する問題です。C35 より保存条件が強いので、別の構成を使います。

まず各点の「ここだけ1」を共有して作る

点 z のアドレスと一致するときだけ 1 になる回路を δ_z とします。各点に別々の長い AND を作ると O(kn) ゲートですが、アドレスの共通部分を接頭辞木で共有できます。

ラベルが 0 の点の δ を OR したものを D₀、1 の点を OR したものを D₁ とします。両方のラベルがある場合は、

で指定どおりに変更できます。区間外では両マスクが 0 なので C が残ります。全ラベルが1なら C∨D₁、すべて0なら C∧¬D₀ とし、空の OR を作りません。

全 completion 回路に難しい情報を持たせたつもりでも、単純な補完回路が残ることがあります。まず、それを作って確かめます。

明示的な長さ k≥1 の prefix u を渡されたら、u の中で 1 の位置だけを一致判定し、OR します。すると、先頭 k 点は u と一致し、残りが全部 0 の回路 D_u を作れます。

なぜ抽出器だけで SAT が解けるのか

φ から u_φ を作り、先ほどの自明な D_u を構築します。s≥B なので、それはサイズ制約を満たす正しい補完です。E に渡し、返された割当てを φ に代入して検証します。

φ が SAT なら、仮定により必ず証人が出ます。UNSAT なら正しい充足割当ては存在しないので、検証が拒否します。E が全域で多項式時間に停止するため、全体が多項式時間の SAT 判定器になります。

現在の候補には、PAP（Proof Analysis Problem、証明解析問題）を使って、completion 回路から元の SAT の証人を取り出す計画があります。先行研究が与えるのは、特定の形の明示的な証明を入力にした抽出です。[6]

先行定理が与える部分

Resolution は、たとえば (A∨x) と (B∨¬x) から (A∨B) を導く証明規則です。空の節まで導けば、不充足の反駁になります。PAP の結果では、「φ に所定の短さの Resolution 反駁がある」と表す式 Ref_r(φ) に対する Resolution 反駁 π を解析します。

n 変数・poly(n) 節の φ、r≥n³ といった原論文の条件の下で、φ が SAT なら、その明示的な π から充足割当てを poly(n,r,|π|) 時間で取り出せます。ここでの |π| は展開された証明の長さです。

小さな回路が指数長の証明を出力する場合、「回路記述は小さい」というだけでは、poly(|π|) 時間の解析器を高速にはできません。圧縮された証明一般を短い記述から全域多項式時間で解析する仮定は、関連する既知結果との合成で P=NP を含意するほど強くなります。これも抽出器の無条件不存在ではありません。[7]

完成しても、何が結論になるのかを先に確かめる

記号による証明に加え、小さい入力で構成を全数検査しました。さらに、式木に限定せず、途中の値を共有できる一般の DAG 回路を、指定サイズまで完全列挙しました。

区間検査の各評価行は、入力点と元回路の出力 c∈{0,1} の組です。両方の c を調べることで、任意の元回路を点ごとに含みます。「n≤4 の元回路を構文まで全列挙した」という意味ではありません。

列挙の「完全」は、どこまでか

n=2 は全関数を覆いました。n=3、4 は、指定サイズ以下で実装できる全関数を覆ったという意味です。それを超えるサイズの分布は、この列挙では分かりません。

二方向の境界に達する、二つの小例

n=2、i=3、s=3 とします。入力順序は 00、01、10、11。w=popcount(3)=2 です。

OR から反対の次値を持つ関数までの最小サイズ差は 3=w+1、NOR からは 2=w。したがって C35 の二つの追加上界は、この例ではそれぞれ達成されます。

手元で再現する

標準 Python のみを使う検査コードと、実行済みの JSON 結果をまとめました。ダウンロードはこのページ内のデータから行います。

収録：4本の Python、次ビット・区間変更の結果、n=2/3/4 の有限回路台帳、照合結果、実行手順と SHA-256 一覧。

python verify_nextbit_patch.py --max-n 4 --output nextbit_patch_verification.json
python verify_ordered_patch.py --output ordered_patch_experiment.json
python tiny_wc_synthesis.py --n 2 --size 4 --out tiny_wc_synthesis_n2.json
python tiny_wc_synthesis.py --n 3 --size 5 --out tiny_wc_synthesis_n3.json
python tiny_wc_synthesis.py --n 4 --size 4 --out tiny_wc_synthesis_n4.json
python verify_tiny_wc_synthesis.py

時間制限や実行環境によって列挙を完了できない場合があります。出力の complete_through_size を確認し、未完了の層を完全列挙と数えないでください。

似た用語が出てくるだけでは、定理を移せません。入力形式、回路の基底、表現の制約、時間と空間、量化をそろえてから接続します。

文献は版によって定理番号や主張が変わることがあります。TDD は正式な SAT 2026 版を使い、PAP は更新版の条件を確認しています。Vyas–Williams には会議版の一定理に関する著者訂正があり、旧版だけの一般化は避けています。[12]

三つの障壁は、適用範囲を確認するために使う

WC 用に「次の正しい小回路を返す特別な oracle」を更新器へ与えれば、更新は容易になります。これは通常計算の上界ではありません。その強い oracle を与えてもそのまま成立すると称する、情報量だけの下界論法を検査する例です。入力と証人の oracle を対称に拡張する通常の相対化とは、同じ操作ではありません。

研究の過程で価値があったのは、解決に近づいたと感じることだけではありません。どの主張が弱すぎるか、どこで条件を落としたか、何を証明すれば次へ進めるかが、具体的になりました。

確定した補題

• C20：P=NP を仮定した効率的な WC の構成。既知構成の直接の系。
• C33：偽の後件 Q に対する (H⇒Q)⇔¬H という論理監査。
• C34：既知結果から P=NP⇒NEXP⊄P/poly。導出は補遺。
• C35：次ビット変更に追加 w または w+1 ゲートで足りる。
• C36：連続区間の変更に追加 3k+3n−3 ゲートで足りる。
• C37：明示した大きな閾値と全域抽出の条件なら、抽出器だけで P=NP が従う。
• C38：全証人抽出が与える向きは W⇒P=NP。単独で ¬W は得られない。

反証された橋

• P で評価できる関数なら、常に小さい OBDD があるという一般原理。
• MCSP の残余数だけで、poly(s) を超える空間を強制する MREC。
• 標準的な代表を一つ選ぶ規則の難しさを、そのまますべての選択規則へ移す推論。
• 証人抽出と効率的な WC の合成から、直ちに WC の無条件不存在を結論する推論。

C33 の Bridge-0 条件文そのものと、一般の implicit-PAP 抽出器の存在命題は、この欄へ「無条件反証」として戻しません。以前の誤った分類は、今回の訂正を優先します。

未証明命題

• P=NP、P≠NP のいずれも未証明。
• 所定の固定 s とモデルで、すべての一様な poly(s) 資源の WC を排除する下界。
• SAT からの prefix 生成と、全ての小 completion を対象にした witness binding。
• 小回路から短い明示的な証明を作る PAP compiler、または厳密に限定した像に対する効率的な解析。
• ここで提示した初等的な構成の学術的新規性。

次の実験

まず、有限列挙で見つかった二例から、入力長を変えても述べられる構造命題を一つ作ります。cut の族、閾値 s、最小補完サイズ τ を固定し、どの条件で次の値が強制されるかを証明または反証します。

命題カードには、入力長 |φ|、変数数 n、表長 N=2ⁿ、prefix 長 k、閾値 s、基底、oracle、停止条件、多項式の依存先を記します。計算実験を大きくすることに加えて、仮説のどこを壊せば偽と分かるかも、先に決めます。

上位の計算量クラスで強い回路下界を得ても、それだけで P≠NP に戻れるとは限りません。研究の途中で、ここにも訂正が必要でした。

量化の順序も変えない

二つは異なります。後者は NP⊄P/poly、従って P≠NP を与えますが、前者から量化を交換して後者を得ることはできません。アルゴリズムから NP の固定次数の回路下界を得る文献を使うときも、言語と次数の依存関係を保ちます。[19]

残余関数

変数の一部を固定した後、残りの変数に対して残る関数。残余言語は、読んだ prefix の後に付ければ受理される suffix の集合。

completion

まだ未確定の出力も含め、全体を計算する補完回路。既読部分との一致とサイズ制約を課す。

live / dead

指定サイズ内の completion が存在する／存在しない。live はすべての続きが可能という意味ではない。

uniform / 一様

入力長ごとに別の巨大な助言を受け取らず、一つの固定機械が全長を処理すること。

selector / uniformizer

候補が複数ある関係から、正しい出力を一つ選ぶ規則。ここでの uniformizer という数学用語自体は、計算の一様性や効率性を保証しない。

canonical / 標準的な代表

たとえば辞書順最初という追加規則で一意に選んだもの。何か一つを選ぶ問題より強い要求になり得る。

PH / 多項式階層

多項式長の存在量化と全称量化を、固定回数交互に用いる計算量クラスの階層。P=NP なら全階層が P と一致する。

oracle

指定した問題の答えを問い合わせられる補助機構。何を無料で問い合わせてよいかが変わるため、通常計算と区別する。

下界

許されたすべての計算法・表現法に必要な資源の最小限を示す主張。一つの実装の遅さだけではない。

compiler / コンパイラ

ある表現から別の表現へ変換する手続き。ここでは小回路から証明への変換を含む。変換時間と出力長も会計する。

以下は各節で使った原典と公式資料です。新しい研究の網羅一覧ではありません。日付は本ページの資料基準日に合わせ、版が重要な箇所を明記しています。

1. Clay Mathematics Institute, “P vs NP.”公式の問題説明・未解決の位置づけ。
2. Beate Bollig, Martin Löbbing, Martin Sauerhoff, and Ingo Wegener, “On the complexity of the hidden weighted bit function for various BDD models,” 1999.多項式時間で評価できる HWB の OBDD 下界。
3. Simone Bova and Friedrich Slivovsky, “On Compiling Structured CNFs to OBDDs,” arXiv version, 2014.Theorem 7：単調 2-CNF の指数 OBDD 下界。
4. Adnan Darwiche and Pierre Marquis, “A Knowledge Compilation Map,” JAIR, 2002.表現の簡潔さ、問い合わせ、変換の区別。リンクは著者公開版。
5. Dylan M. McKay, Cody D. Murray, and R. Ryan Williams, “Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes,” STOC 2019.Theorems 1.2–1.3、§2.1 Circuit-Min-Merge。本ページ C20 は一ビットごとの証人保持への明示的な適用。
6. Noel Arteche, Albert Atserias, Susanna F. de Rezende, and Erfan Khaniki, “The Proof Analysis Problem.”arXiv v2（2026 05 19）、Theorem 1.1 と Corollary 5.6。明示証明からの抽出。
7. Noah Fleming, Stefan Grosser, Toniann Pitassi, and Robert Robere, “Provable Reductions in TFNP.”implicit Resolution などの関係。著者公開PDFの Theorem 1.1 も照合。
8. Guy Van den Broeck and Adnan Darwiche, “On the Role of Canonicity in Knowledge Compilation,” AAAI 2015.固定 vtree と reduced SDD における正規性・更新の制約。
9. Florent Capelli, YooJung Choi, Stefan Mengel, Martín Muñoz, and Guy Van den Broeck, “A Canonical Generalization of OBDD,” SAT 2026.正式版 Theorems 11,16,21。HWB 下界の Theorem 21 は n が7の倍数という条件を持つ。
10. Christoph Berkholz and Matthäus Micun, “Proof Systems Based on Structured Circuits,” SAT 2026.Theorem 13、Lemma 23。表現下界と制限付き証明過程の接続。
11. Lance Fortnow and Joshua A. Grochow, “Complexity Classes of Equivalence Problems Revisited.”不変量・代表元・辞書順最初の代表の違い。
12. Nikhil Vyas and R. Ryan Williams, “On Oracles and Algorithmic Methods for Proving Lower Bounds,” corrected version / erratum, 2024.会議版の Theorem 1.10 に関する著者訂正。訂正後の適用範囲を確認する。
13. Theodore Baker, John Gill, and Robert Solovay, “Relativizations of the P=?NP Question,” 1975.P=NP と P≠NP をそれぞれ満たす oracle の存在。
14. Alexander A. Razborov and Steven Rudich, “Natural Proofs.”擬似乱数仮定と、constructivity・largeness・usefulness の三条件。
15. Scott Aaronson and Avi Wigderson, “Algebrization: A New Barrier in Complexity Theory.”代数的 oracle 拡張による障壁。
16. Lijie Chen, Yang Hu, and Hanlin Ren, “New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String,” ITCS 2026.Missing-String からの障壁。WC 全般の不可能性としては用いない。
17. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson, “In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time,” JCSS, 2002.§4.1。NEXP⊆P/poly⇒NEXP=MA。
18. Oded Goldreich and David Zuckerman, “Another Proof that BPP ⊆ PH (and more),” 2016 revision.C34 で使用する MA⊆PH の確認。
19. Cody D. Murray and R. Ryan Williams, “Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP.”Theorems 1.1–1.2。固定次数の下界と言語の依存関係。