最近、ミレニアム未解決問題の一つがAIによって解決されたという情報やその過程が世間を騒がせている。特に今後の数学の在り方について、様々な意見が表明されており、私は毎日興味深く拝聴している。この流れに乗じて、P vs. NP問題（ひいてはその分野）は現状どのような状況なのかについて解説したい。この記事は読むのに数学の前知識は不要で、専門用語が出ても流して読むことができるであろう。ちなみにこの記事の文章はAIを全く使っておらず、私がキーボードを叩いて書いている。
一応、私はこの分野（理論計算機科学、より狭くいうと計算量理論）では世界的に最前線の研究者であると自負していて、実際に世界最高峰の国際会議（STOCとFOCS）でこれまで何本も論文を発表し、実際に世界トップの多くの専門家と交流がある。これから書く内容は個人的に思っていることだが、多分同様の立場の人も大体同じように考えると思う。ただ、私自身が何らかの組織のトップにいて分野全体の方向性に影響力を持つとか、分野全体を代表するつもりではないことには留意してほしい。あくまでも「計算量理論の一人のプレイヤー」としての視点とであり、専門家の中には私と違う意見を持つ人だって普通にいるであろう。なお、この分野に詳しい人からすると特に目新しいことは何も書いてない。
かなり保守的な前置きになってしまったが、結論からいうと 現状の人類はP vs. NPは解決からあまりにほど遠く、世界トップレベルのほとんどの専門家はたぶんP vs. NPの解決を直接的に取り組んではいないであろう という現状である。かなり強い表現をしているが、みなさんが想像しているよりも遥かに進捗がないのである。また、究極的にはP vs. NPに行き着くかもしれない方向の研究もあるが、実際にその最終地点までの距離は途方もなく長い。
なんなら、「P vs. NPを示すために越えなければならない三大バリア（障壁）」がある。具体的には相対化のバリア、代数化のバリア、自然な証明のバリア（細かくいうとこれはちょっと違う設定なのだが）と呼ばれるものである。これらは「このアプローチではP vs. NPには辿り着かない」という類のものである。ちなみに「第四のバリアはあるか？」というテーマが2023年に、理論計算機科学の世界的にかなりハイレベルな研究集会で議題になったこともある。つまるところ、なぜ証明が難しいのか自体が研究対象になるほど、P vs. NPは難しいのである。
また、それとは別に「大学研究者」ならではの事情もある。おそらく理論研究者の多くは大学教員なのだが、大学教員は自身の研究を進めていくための予算を競争的資金で賄っている。日本では科研費と呼ばれるものであり、そのためには研究内容や計画を記述した申請書を提出し、それが審査されて選ばれた申請に対してのみ予算がつく。理論系だと自身や指導学生の出張、研究補助者の人件費、学会やシンポジウムの開催、およびPCやその周辺機器などの物品費に充てられる。従って学生や後進を育成するには予算が必要であり、それを獲得するには、自身の研究の重要性や、その実現可能性などを説明することが求められる。大学教員の多くは担当講義や運営業務の他にも自身の研究、そして予算獲得を頑張っており、とてもじゃないがP vs. NPといった解決から程遠い大問題では、よほど有望かつ具体性の見えるアプローチとかでない限り、実現可能性の面から見ても予算も取れないし腰を据えてチャレンジする余裕はないのである。つまるところ、少なくとも計算量理論の研究では、メジャーな未解決問題を解くことよりも、最近出た論文の未解決問題を部分的にでも解決したり、新たに何とか解けそうな設定の問題を考え出したり、その重要性を説明する論文執筆・発表も重要な仕事なのである。そしてそれを分野外にも納得させて、予算獲得に繋げて、さらなる分野の発展を目指すという営みが繰り広げられている。他の分野ではどうかは分からないが、数学に近しい理論研究はこんな状況だと思う（今後AIによってこの部分は変わっていくかもしれないが）。
そもそも P vs. NPとはどういう主張なのだろうか？なぜ難しいのだろうか？
計算量理論は計算の「量」を明らかにする理論なのだが、その量が少ないことを効率的という。すなわち、少ない手間で問題を解くにはどうすれば良いか？を考えるのである。そして、その問題を解く手続きのことをアルゴリズムと呼ぶ。例えば電卓を使って計算を進める場合、その電卓でボタンを叩いた回数を計算の量としてみなしたりする。特に代表的な研究対象は判定問題と呼ばれる問題である。判定問題とは「はい」「いいえ」で答えられる問題のことである。そして、効率的に解ける判定問題を総称してPと呼ぶ。
推理小説のクライマックスで探偵が事件の犯人やトリック、および証拠を明らかにする場面を想像してもらいたい。読み進めていくと、探偵の推理の内容が最初から最後まで正しく、そしてその証拠が犯人の正体を指し示すことを納得できるであろう。逆にその探偵がヘッポコで、出鱈目な推理を披露したならば、どこかに矛盾があるはずであり、読者はそれに気づくはずである。ここで「犯人はAさんであるか否か？」という判定問題を考えてみよう。答えが「はい」であれば、探偵が正しく推理と証拠を提示すれば実際にAさんが犯人であることを簡単に検証でき、答えが「いいえ」であれば、探偵がどんな推理を述べようがどこかで矛盾を検出できる。このように、答えが「はい」ならばそれを支持する証拠が存在し、答えが「いいえ」ならばどのような証拠を持ってきてもそれが嘘であることを見破れるという性質を持つ判定問題の全体をNPと呼ぶ。
つまり、P vs. NPとは、「効率的に解ける判定問題の全体」と「効率的に検証可能な判定問題の全体」が一致するかどうかを問うているのである。推理小説の例でいえば、「任意の推理小説のトリックは簡単に見抜けるか？」という問いだと思えばよい。これは、NPに属する判定問題がPなのか？（効率的に解けるか？）ということを意味する。
このように、P vs. NPは直感的にはとても理解しやすい（厳密な定義を理解しようとするとチューリング機械から学ばなければならないが）。そしてその「嘘証明」が頻繁にarXivなどに公開されている。この分野で最も権威のある学術雑誌 Journal of the ACM (JACM)や関連雑誌には P/NPポリシー というのがあって、例外はあるものの、P vs. NPやそれに関する重要な予想の解決を主張する論文は2年に1回しか受け付けないようになっている。ちなみに P=NP を主張しており、かつLean-verifiedな証明を提示している論文を最近私は見かけた。
多くの研究者は P と NP は違うと思っている。これは NPに属する判定問題であって、Pに属さないものが存在することを意味する。つまり、P≠NPを示すには、「効率的に解けない」ということを証明しなければならない。一般に「できる」の証明は実際にやって見せれば良いが、「できない」の証明はそうはいかず、とても難しい。計算量理論では「効率的にできない」ことを示す手法が非常に限定的なのである。現代の計算量理論では「効率的にできない」ことをどう応用するか（例えば暗号解読の困難性）や、計算機のモデルを分散計算など実用のものに近づけたり、量子計算ではどうなるかなど、様々な問題設定における「計算の限界」を議論している。
なお、現代的な計算機が誕生したチューリングの時代では、理論上、有限時間で解けない問題が存在することが示されている（停止性判定問題）。これと同様の議論を使えば、効率的に解けない問題も存在することが証明できる。ただしこのような限界性の証明は、特定の問題に対してのみ機能するものの、検証可能な性質を持つ問題には拡張できない（相対化のバリア）ことが示されている。
では、そもそもなぜ P vs. NPを示すのはこんなに難しいのだろうか？結局のところ、「計算の限界をどう証明するかは何も分かっておらず、世界中の賢い人たちが長年一生懸命取り組んでもなお、全く解決の糸口が見えない」に集約されてしまう。P vs. NPには、それと関連して星の数ほど多くの未解決問題が残っており、例えばP≠NPの百歩手前のP≠PSPACEといった予想に対しても解決の糸口は何も分かっていない。
でも「昨今はナビエ=ストークス(NS)をAIが解いたというアナウンスが出たじゃないか。P vs. NPもAIが解くんじゃないのか」と言いたくなるだろう。正直私は他のミレニアム未解決問題については背景から何まで素人なので、どういう状況にあるのかは知らない。おそらくP vs. NPと同じで、難しすぎて世界トップの専門家はちゃんと真面目に取り組んでいないけど、AIが出し抜いてしまったのかもしれない。そしてそのような出し抜きがP vs. NPでも起こりうるかもしれない。ただ、P≠NPの証明がもし与えられたとするならば、それは現状の全てのバリアを突破する革新的なものになるに違いないのは確かである。「証明ができないことを証明しよう」といったメタ的な方向性に研究も興るのは、計算量理論ならではの面白い風潮だと思う。私としては、P vs. NPの百歩手前の大量にある計算量理論の未解決問題たちをAIが解いてくれるのを期待したいところである。もし解けたとしたら、それを皮切りに P vs. NPへの糸口が掴めればと思う。これを踏まえると、分野的にどういった問題がなぜ重要視されているのかということを知っている専門家が細かくプロンプトを与え、もしAIが証明を提示したとしたらそれを検証し、分かり易くまとめて正しさに関して責任を持つといったことが大切になり、やはり理論研究者は職を失うということには全くならないだろうと思う。
ちなみにAIが与えた証明を論文にすること自体は、2026年9月時点では、ちゃんと書けてさえいれば論文として認められてる風潮にあると思う。少なくとも「AIが証明をやったからrejectする」という国際会議は、ある程度のレベルがある計算量理論関連の分野では見当たらなかった。こと論文を発表するという状況においては、反AIなスタンスをとる専門家は自分の知る限りでは見たことはない（もちろん「人間ではなく機械的に証明が与えられる」ことに関する空虚さや、密かに進めてた研究がAIに先越されるなどの憂慮を持つ人は多いだろうし、今後も活発に議論されるだろうが）。ただ、AIが論文においてどのような貢献をしたかを表記せよという「AIの明示 (AI disclosure)」のルールがある。
