第一問 P vs NP Problem
♦
十六世紀、数学は神に挑戦した。
コペルニクスが天動説を唱えたころ、数学はまだ自然科学との境目がなく、人智及ばずの領域に人智で挑む唯一の武器であった。
この世に起こる事象はすべて神が創造し、操作している？ そんなことはあるものか、と、恐れ多くも人類は、一定の入力があれば固定の出力があるという数式を予想し、仮説を立て、実証した。
少しずつ、少しずつ、現象を神の所轄から奪い、人間のものにしていった。
しかし怒りに触れたのか、はたまた怖気づいたのか、勢いはそこまであった。
いつからだろうか、神や自然を解き明かす科学であることよりも、数学は数学であることを求め始めた。
やはりドイツのせいだろうか。フリードリヒ・ガウスという絶対的な存在を生んだ国だ。エルンスト・クンマー、カール・ワイエルシュトラス、レオポルト・クロネッカーら三大数学者らが育つ土壌は十分だった（クロネッカーについては、学者というか、銀行や農場の経営をしていたので邪道ではあるが）。そしてダフィット・ヒルベルトが二十三の問題を制定し、数学は、神への対抗という宗教色を消し、学問として確立してしまった。
いや、フランスの責任だろうか。ピエール・ド・フェルマーは裁判官の傍らで数学をたしなみ、ブルーズ・パスカル、ルネ・デカルトと交流した。シモン・ラプラスは光の速度を求めたし、ギュスターヴ・コリオリは転向力を求めたし、ABC予想を提起したのもジョゼフ・オステルレだ。あぁ、しかしジョゼフ・フーリエは歴史に傾倒し、後継したフランソワ・シャンポリオンはロゼッタストーンを解読するに至った。
勢いはなくなったとは言え、彼らの理論を使えば、もう一度、チャンスはあるだろう。神に挑戦？ いや、もっと別の問題に、だ。
今から四つの問題を出そう。これを解けるなら百万ドルを出したっていい。まずは一つ目だ。
総当たりで解ける問題と、総当たりではとても解けない問題があるとしようじゃないか。
とても解けない問題の例は、そうだな。きみがパソコンやスマートフォンに不用心に入力しているパスワードを思い出してくれ。データ送信中に守るために、三百桁同士の素数を掛けた暗号コードがかけられるのだが、さすがにそんな桁数は、いくらコンピュータを使っても計算が追いつかないから、きみは気楽にネットショッピングができるわけだ。これが、総当たりじゃ解けない、正確には、とても時間が足りない問題ってことだ。
もし、それを解けるだけの時間をかければ、総当たりなら解ける問題なんて簡単に解けるわけだ。だから、前者は後者の集合には含まれるってこと。
ちょっと待って、って思わないか？ じゃあ、コンピュータの計算能力が上がれば、つまり時間が短縮できれば、集合に含まれるかどうか以前に、前者は後者とイコールになっちゃうってことに。そうなると大変だ。きみを守っている素因数分解は、解けてしまう問題になってしまうわけだ。
分かっただろう。この二つの問題は、決してイコールになっちゃいけないんだ。
イコールにはならないって証明しなきゃいけないんだ。
さぁ、本題だ。百万ドルに向けて、一問目だぜ。気合を入れな。
小学生は大人ではない、と証明してくれ。
