2016/10/25

【読書メモ】 P≠NP 問題

 『 P≠NP 問題 野崎昭弘・著 講談社Blue Backs』
本書を手に取った直接の理由は、何気なく立ち読みしていたさいに不定方程式の解判定のくだりに惹き込まれ、さらに別ページにては、合成数(素数)の計算プログラムにおける非決定性云々に、クスリと笑わされてしまったこと。
ほほぅ、そうかなるほど、と頭から読みとおして…いや、本書はこれまで手にしたどんな新書版よりも難しい、やめときゃよかった!僕の見識ではとても読みとおせるものではない、だいいちサブタイトルは「現代数学の超難問」とな。
それでも僕なりの頭で概括すれば ─ きっと本書が呈する主題は、「数理問題の特性とくに難しさを、そこでのアルゴリズム(計算手順)の論理仕様を以て定量的に判定」 するこころみであり、それらの様々な事例紹介をとおして難問の世界に読者を誘う、というところではないか。

本書のみならず、数学について書かれた本では、面白いことに学術タームの日本語表現があいまいに映り、たとえば 『問題』 と 『解』 とその 『解法アルゴリズム』 の論理上のかかわり、とくに 『…という問題のアルゴリズム』 といった表現における助詞の 「の」 がいつも判り難い。
尤も、これらのかかわりについては、むしろ数式や計算プログラムから直観した方がピンとくる(だから此度の読書メモにても僕なりの直観に則って記してみた、まあ大筋は正しいだろう)。
とくに、数学やコンピュータ設計に通じている読者ならば、引用されている数式などを参照しながら読み進められた方が、主題と真意をいよいよ直観的に汲みやすかろう。
※ とりわけ、数学問題へのアプローチ例のほか、チューリング機械のデータ処理基本フローやループ問題、さらにオイラー路やハミルトン路の図示、そしていわゆる非決定性チューリング機械における数理計算の検証例など、パズリングな引用の数々。

なんにせよ、以下の僕なりの読書メモにては、あくまで総論概括を列記するに留めることとする。


コンピュータの高速化と巨大化を追求のため、特定のハードウェアにもプログラム言語にも限定されない、論理的に最も効率的な「アルゴリズム(計算手順)が追求され続けている。

<現在のアルゴリズムの主な評価尺度>
「時間計測量」: たとえば2つのデータ x,y を x≧y という大小関係として判定するような、特定の計算において、その計算ステップの実行回数を数値化したもの。
「サイズ」: たとえばn元連立1次方程式の n や、n次多項式 f(x)=0 の次数 n など、計算量に影響を及ぼす規模の数値。
「多項式時間」: とくにサイズ n の多項式でおさえられる時間計算量。
「指数関数時間」: サイズ n の指数関数でおさえられる時間計算量。
(※ p.116 に問題のサイズ(オーダー規模)と時間計算量のマトリクスあり。)

<必要なアルゴリズムと計算量に基づいた、問題の難度クラス分け>
クラスL: アルゴリズムが、或るサイズの1次式(対数や平方根ふくむ)に収まり、簡単に解を導ける計算量の問題群。
サイズのみならず、一定時間内に解けること明らかな計算量問題も含まれる。
クラスQ: これはクラスLの問題を含み、さらに、アルゴリズムの計算量が或るサイズの2次式に収まる問題群。
たとえば数値データを整列する問題など。
クラスT: クラスQまでの問題も含みつつ、さらに、アルゴリズムの計算量が或るサイズの3次式に収まる問題群。
クラスP: クラスTまでの問題も含みつつ、さらに、アルゴリズムの計算量が或るサイズの多項式に収まる問題群。
或るアルゴリズムがここまでのクラスに属することが、サイズを問わず解を判定するための必要条件である。

クラスEXP: クラスPまでの問題も含みつつ、さらに、アルゴリズムの計算量が或るサイズの多項式を指数とする関数に収まる問題群。
たとえば、或るサイズの入力を以て指定された入出力関係を満たす、最も簡単な電子回路の設計難度レベルであるが、このクラスになると、サイズ次第では計算量が爆発する恐れアリ。
クラスS クラスEXPまでの問題も含みつつ、計算量はともかくとして、有限時間内に解きうるであろうアルゴリズムの問題群。

※ なお、このクラス階層分類のさらに外縁に、解くためのアルゴリズムが存在しないであろう=つまり一般的にみてどうしても解けないであろう問題群が、無数にある。

===========================================

数理計算問題の難しさを、解法アルゴリズムの有/無を以て確認するため、とくに何らかの解の存在判定を目的とする計算問題をおく。
これをいわゆる「決定問題」と称す。
※ とくに任意定数a,b,c,dなどを含む数学的な問題群を、決定問題の論考における足がかりに据えている。
一方、実際の解の算出や最適化の提示を求める問題は、「決定問題」には含めない。

<決定問題と、解法アルゴリズムの関係(例)>
・ヒルベルトによる第10問題。
「指定された不定方程式が整数解を持つか否か、そこを判定する"一般的な"方法はあるか?」
むろん、1次の不定方程式の場合に限れば解法アルゴリズムが在り、必要十分条件の定理として、定数項が係数の最大公約数で割り切れればよい(ユークリッド互助法で確認出来る)。

・一般的な解法アルゴリズムが在る、と見做せる決定問題であれば、1930年代以降のいわゆるチューリング機械の応用系にてそれを定式化=実証出来る ─ ということになっている。

・だが併せて、チューリングによれば、そもそも「ヒルベルト提起の決定問題には、定式化どころか、そもそも原理的に一般化出来ず、解法の有無判定すら出来ない問題も『ありうる』」由
(上の問題クラス分類でいえば、クラスSのさらに外側の問題にあたる。)
チューリング機械においては、或るプログラムが実行停止した際にそれが論理ループによる異常終了か否か、その判定をそのプログラム言語自体で確かめることは出来ない、とされている (プログラムの停止問題)。

なお、不定方程式についていえば、ずっとのちになってマチャセヴィッチが 「不定方程式の解の存在を判定する一般的な解法アルゴリズムは無い」 と定理済み。

・経路図の「グラフ」に関わる問題例。
経路図を節点(node)と辺(edge)を以て表現すると、とくに全ての辺を一度ずつ通る単純経路がいわゆる「オイラー路」で、この存在判定の必要条件は、辺が奇数本集まっている点(奇節点)が0または2個しかないこと
しかし併せて、この経路のどの節点もなんらかの経路で連結されてこそ、オイラー路存在の十分条件を満たすといえ、ここまでは、オイラー路の存在判定のための必要十分条件でとしてアルゴリズムが定理化されている。
なお、特に奇節点が0の図は「オイラー閉路」と呼ばれる。

・だが、やはり経路図のグラフについて、有名な問題に 「ハミルトン路」 がある。
こちらは存在判定のためのアルゴリズムが無く、存在判定には総当たり方式による経路探ししかない。
とくに出発点と終点が同一であるものを、「ハミルトン閉路」という。
この「ハミルトンの閉路」の存在判定アルゴリズムは、上分類のクラスEXP内に属していることは分かっているが、クラスPにまで属しているかどうか分かっていない。

=========================================

<非決定性アルゴリズム>
「決定問題」にては、その解法アルゴリズムの有/無判断をウヤムヤにしてしまうインチキアルゴリズムも混じり、それを特に「非決定性アルゴリズムNon-determinisitic Algorithm」という。
コンピュータプログラムにて、この非決定性アルゴリズムの介在を直接確かめることが出来る。
(そもそも、乱数を利用しないコンピュータプログラムは、決定性アルゴリズムだけで走る ─ はずである。)

その具体例は、「自然数 n (<2) が合成数かどうか?」を確かめる計算プログラム。
ここで n>k>1 の有限範囲にて任意の k を選ぶさいに、決定的な要件指定ナシに自由な数をおいており、ここは「非決定性」のステップである。
たとえ、その先の条件分け 「n を k で割った余り d が0か否か」 が決定性のステップでなされているにせよ、プログラム全体としてはあくまで「非決定性アルゴリズム」の実行というべきである。

しかも、この非決定性アルゴリズムの実行プログラムにおいて、結果的に最小の「時間計算量」をもって、アルゴリズムの実行力を評価している。
さらに、この同じ計算プログラムにて自然数 n が素数であった場合には、「n を k で割った余り d が0か否か」 のところで答えが No となり、計算が繰り返されることになる、が、このケースを無視してアルゴリズムの実行力を評価している。

以上にみられる不完全さにも拘わらず ─
非決定性アルゴリズムが何らかの解を出力する場合には、これを一応は認めつつ、その最小時間計算量を「非決定性時間計算量」と限定的に定義する。
そして、この非決定性時間計算量が何らかの「サイズ」の「多項式」で収まる問題クラスを、「非決定性アルゴリズム(Non-determinisitic Algorithm)にて多項式時間(Polynomial time)で解ける問題、つまりNP問題という。

このNP問題のクラスは、上の分類にてはクラスPをすべて含みつつクラスEXPの内に存在する─ことにされている。
上に記した「自然数 n (<2) が合成数かどうか?」 の問題は、非決定性アルゴリズム抜きと見做せばクラスPの問題だが、じっさいには非決定性アルゴリズムが含まれていることは明らかなので、クラスNPの問題とされる。
さらに、ハミルトン閉路の問題も、その計算にては非決定性アルゴリズムの要素を無視しつつも、多項式のサイズを勘案すれば、クラスNPに属した問題だといえる。

なお、クラスNPの内におかれつつ、クラスPには無いという、そんな問題は「ひとつも見つかっていない」。
ということは、問題クラスがPと問題クラスNPは、もしかしたら同じ問題なのかもしれない。
この疑義を P≠NP 問題と称している。

=================================================

以上