第一章
序論
1.思想的背景
奇しくも、昨年は「2001年宇宙の旅」の年。
実は、「P=NP?」問題については、発表のタイミングを図っていました。
この点、映画の「A.I.」と通じる処がある。
1999年7月にも、どうしようかと迷ったのですけど、印象が悪いので次回を待ちました。
冒頭、いきなり何を言いたいかというと、この難問の解決は、社会に対し、ノストラダムス予言以上のインパクトを与える可能性があるという点です。
どのくらいのインパクトか?
アカデミックな社会において、「ハルマゲドン」が勃発したぐらいのディープインパクトだと言っておきましょう。
実際、この本が出版されるまでに、某掲示板で発生した騒ぎは、科学史上、貴重な資料として後世に残ることでしょう。
(著者の私が残します。)
こういう隠喩で、何となく、現時点での、雰囲気を察してもらえると思います。
但し、こう言ったからといって、決して暗い印象ではありません。
あくまでも、明るく、知的癒し系のノリで、この本を読み進めることができると思います。
内容の難解さに対し、表現は軽く、判り易くを心掛けました。
で、肝心の、内容です。
素人には、ダイヤモンドと水晶とガラス玉の区別がつきませんね。
いくら“屑ガラス”じゃないと説明したところで、せいぜい、
「占い師の“水晶”ぐらいの御利益だろう」
と思う程度です。
「そんな大きなダイヤがあるはずがない。あれば博物館入りだ。」
という先入観があるはず。
しかし、どのダイヤも、最初の原石は博物館にはありません。
だが、そういう事実をいくら強調しても、中々、信じてはもらえない。
というわけで、この節では、結論を得るまでに通過しなければならなかった、様々なバリヤ、難関の説明をしておきましょう。
但し、この節では深入りせずに、簡単な背景描写だけで済します。
まず、最初に通過しなければならない難所の解説から。
今まで、「P=NP?」問題は、まるで、「アルゴリズムの定義」を彷彿とさせるかのように扱われてきました。
「異なる多数の実例が同一の“NP完全”概念に属する。しかも、現時点までに、NPをPにするアルゴリズムは見つかってない。よって、多分、P≠NPと見ても良いだろう」
という結論ですね。
「アルゴリズムの定義」の場合は、
TuringのTuringマシン、Kleeneのリカーシヴ関数、Postの正規システム等々、
そうそうたる才能が候補者に名乗りを挙げました。
これらが総て同値ということで、Churchが「アルゴリズムの定義」に採用して決着を付けたという歴史的経緯があります。
しかし、「P=NP?」問題の場合は、直感の優れたChurch役はいませんでした。
だから、“多分「P≠NP」”なんていう偏見が徘徊していた。
そこへ、著者が華々しく登場したわけです、「P=NP」だと言って。
しかも、証明してみせた。
Church以上の役者ぶりです。
科学史的に言えば、ある分野の“コンセンサス”がひっくり返された例は結構あります。
しかし、これほどインパクトのある登場例は、今後、もし生起するとすれば、
「アルゴリズムの定義変更」
か
「公理的集合論(ZFC)の矛盾」
ぐらいのものでしょう。
だれか、どちらかに挑戦してみますか?
通常の数学的難問程度では駄目ですよ。
その分野の専門家のコンセンサス(「多分、こちらの方だろう」)が出来ていませんもの。
コンセンサスを引っくり返さなくっちゃあ!
少なくとも、難問認定されて、懸賞金が懸かってなければ話になりません。
以上の意味で、「P=NP?」問題の解決は、
「歴史上、何時、誰が、100メートルを9秒きって走るか、そもそも、人類に可能か?」
というレベルの話題だということが納得できたと思います。
さて、以上の準備の下、ここで、やっと、第一難所の背景説明ができます。
単に、クドクドと自慢話をしていたわけではありません。
実は、「P=NP?」問題の解決には、アルゴリズムの定義が関与してきます。
アルゴリズムの定義は、すでにChurchで完了しており、口を差し挟む余地は無いと思う研究者。
本当に、そう思いますか?
この本を読むことで、その種の先入観が瓦解することを、この場で先行指摘しておきます。
少なくとも、計算量理論の研究者にとっては、目新しい見解が披露されます。
「P=NP?」問題は、この本で指摘される「アルゴリズム同定問題」と関連してきます。
「アルゴリズム同定問題」の意味の深さは、本文を読んで納得してください。
いわば、「アルゴリズム同定問題」が「P=NP?」問題から“創発”するのです。
さて、次の難関の背景説明に移りましょう。
この世には、ある種の問題を解くのに、その業界の、それまでの常識的な解決法が通用しない場合があります。
厳密な数学の世界においてすら、このような現象は生じます。
歴史的な代表例として、集合論の分野における“選択公理”や“連続体仮説”がありますね。
これらの問題は、通常の数学的定理のように「正しいかどうか?」ではなく、「独立している」という形で“最終的に”解決されました。
これと同じような現象が、計算量の分野で生じても決して不思議ではありません。
ここでの問題は、「P=NP?」問題です。
果たして、この難問は、「正しいかどうか?」で解決できる種類の問題なのでしょうか?
これに対する最終解決をするのが、ここでの目的です。
これが出来れば、文句なしの“神業”でしょう。
将に、ピカピカの歴史殿堂入りです。
結論を述べておきますと、「P=NP?」問題は、「独立」で解決できる種類の問題ではありません。
では、どのようにして、最終解決可能なのか?
中身は次章以後のお楽しみ。
ここでは、そちら方面の話題が目的ではありません。
「独立性」の証明には、それまでに無かった種類の手法(「強制法」)を必要としました。
このテクニックを理解するのは、少し(人によっては、かなり)ハードです。
それと同様のことが、ここでも起きます。
但し、「強制法」では無理ですよ。
まったく新しい種類の方法論が必要です。
この方法論こそ、「状況依存性」です。
(詳しい内容は本論で。)
従来も、「状況依存性」なる概念は様々な分野で使用されてきました。
しかし、何となくピンとこなかった。
その理由の一つに、「状況依存性」なる概念に対するバックボーンというか、背景・核になるキチンとした理論が存在してなかった所為があります。
もう一つには、この概念を使用した際の、現実的な御利益が確認できなかったのです。
「状況依存性」で、実質的に、何が有難いのかというわけです。
これに対し、この本において、「P=NP?」問題を解くことで、「状況依存性」の実際的な御利益が確認できました。
さらに、「状況依存性」の背景理論である、「状況理論」まで、すでに完成間近であることが宣言されています。
まさに、至れり尽せりです。
歴史的難問の解決には、これぐらいの、用意周到な準備が必要だったのです。
次の関所の背景説明に移ります。
難問に対し、解に至るルートの全ての可能性を如何にして調べ尽くすか。
最終解決の場合、ここがポイントですね。
一気に解けるような問題は、大したことはない。
で、当然、幾つかのパターンに分けて、チャレンジする。
問題は、このパターンの種類です。
例えば、SATを正面から闇雲にアタックすると、とてもじゃないが分け切れない。
しかし、一方、例えば、「4色問題」は有限個のパターン分けに成功して解決しました。
このような実例があるのですから、絶望的というわけでもない。
しかし、分けたパターン数が、数百なんてことになると、アルゴリズムが大変です。
オイオイ、本当に大丈夫なのか?
答えを言っておきましょう。
「P=NP?」問題では、大丈夫です。
それほど多くのパターン分けは必要ではありません。
原理上、無限個の様々なパターンが発生しますが、全体が秩序立っているために、理論的に確認していく作業において、実質的には、3、4のパターンを調べればOKになります。
但し、パターン分けの意味が、従来から想定されて来たものとは違う。
上でパターン分けと言った場合、例えば、SATならば、入力の論理式に対するパターン分けのことですね。
つまり、オブジェクトレベルでのパターン分け。
ところが、ここの証明では、よりグローバルなパターン分けが必要になり、ローカルな論理式のパターン分けは、その陰に隠れます。
つまり、状況依存性に基づくパターン分けです。
こういうのを、「メタレベルのパターン分け」と言います。
ここの所の感覚は、実際に本論を読まなければ掴めないと思います。
次の関所は?
あの「フェルマーの定理」も、最後には意外と簡単に解けましたね。
そこへ至るまでの準備が大変だったわけです。
今回も、そうでした。
なにせ、EXP(1)(この用語は後に説明します。)に匹敵する証明領域を、独自の能力で枝刈りしながら探索し尽くした結果、やっと、解に至る一本の枝を見つけ出したのです。
皆さんが見ているのは、その枝にすぎません。
だからこそ、この枝は、こんな大きな木の中から探し出したのだということを宣伝しているのです。
まさに、“針の穴に駱駝を通す”以上の技。
当然、最終解答へ至るまでに使用する戦略は、それ自身が最終解答の影響力に匹敵するぐらいの、いや、それ以上の重要性、応用可能性を有しています。
で、その戦略。
これが、「パラドックスに基づく証明」です。
この本で採用した方法論は、「パラドックスに基づく証明」の一例になっています。
(筆者の命名です。)
どういう方法か、予想がつきますか?
そもそも、理論にパラドックスが発生するという意味は?
他の理論で、パラドックスが発生した例を知っていますか?
そして、その理論の場合、如何にしてパラドックスを排除・回避したか?
排除できない理論の場合は、一体、どうするのか?
理論全体は駄目になるのか?
実は、こういう種類の課題が発生してくるのです、計算量理論にも。
想像できましたか?
この種の課題に対するヒントとして、自然言語処理の分野の例を挙げておきましょう。
自然言語処理の分野で中心になるのは、何だかんだ言っても、やはり、構文解析でしょう。
これは、かの創始者Chomskyの構文論が理論的支柱ですね。
しかし、最近の構文論は、できるだけ広範囲の文を対象にしようと画策するあまり、何か、天動説を彷彿とさせるようなグロテスクな様相を呈してきたと感じるのは、私だけではないと思います。
構文論だけでは、全ての自然言語を解析することは不自然なのです。
当然、そこには、何らかの意味論も介入してこなければ嘘でしょう。
さらには、その他の文脈依存性とか語用論とかも登場してくる余地がある。
特に、「この文は嘘である」なんて種類の「嘘つきのパラドックス」を構文論だけで処理することは不可能です。
そういう背景のもと、自然言語処理にも、状況依存性の概念が登場したわけです。
で、ここで扱っている計算量理論。
この文脈で比喩を用いれば、「P=NP?」問題は、「嘘つきのパラドックス」まで対象範囲に織り込んだ文章に対比できます。
そして、計算量理論でアルゴリズムによるアプローチを採用するのが自然言語処理における構文論アプローチと思ってください。
さて、初期の(そして、現在の頑固な一部の)自然言語処理研究者は、自然言語処理は構文論で全て解決可能と思っていました。
(上述のように、錯覚です。)
これと類比的に、従来の計算量理論研究者は、「P=NP?」問題の肯定的解決は、アルゴリズムによるアプローチで処理できると信じていたわけです。
ところが、大多数の自然言語処理研究者は、対象文中に「嘘つきのパラドックス」まで登場することが判明した時点で、素直に、構文解析以外の手段を使用せざるを得ないことを認めました。
同様な現象が、計算量理論の分野にも発生します。
つまり、「P=NP?」問題の解決はアルゴリズム的アプローチだけに固執しては遂行できなかったのです。
では、具体的に、どういうアプローチで証明したのか?
それが「論理的アプローチ」です。
さて、最後の難所の背景説明です。
「論理的アプローチ」ルートを通るためには、従来の計算量理論を論理的に再整備する必要性が生じます。
その結果、重要な事実が判明しました。
どういう事実か?
実は、計算量理論は単一の理論ではなかったのです!
採用する「基本原理」の強弱に応じて、様々な種類の計算量理論に階層化される。
この分野における従来の研究者は、こういう論理的事実を想像だにしなかったはずです。
この事実を指摘するだけでも、大金星。
関所の手形としては、十分の貫禄。
さて、論理的に様々な種類の計算量理論に分れるのならば、夫々は、「P=NP?」問題の意味でどうなるのか?
ある階層の計算量理論では、「P=NP」になり、別の計算量理論では、「P≠NP」なんてことはないのか?
更に言えば、ある種の計算量理論では計算量が一意決定不能になる可能性はないのか?
もっと深刻な場合として、計算量理論が論理的に矛盾することはないのか?
論理的に矛盾した理論では、何でも主張できますね。
とういことは、その種の理論内で、SATのPアルゴリズムを云々しても、意味がありません。
また、計算量が一意決定できないような理論内で、SATのPアルゴリズムを追及しても、「P=NP?」問題の解とは言えない。
つまり、この種の理論上では、「P=NP?」問題は消滅するのです!
どうですか?
事態の深刻さが認識できましたか?
余韻を残しつつ、この辺りで、背景説明を終了しておきましょう。