計算困難性とP≠NP予想

以下の図をみてください。次のような点と線から構成される構造を、数学ではグラフといい、様々な構造を抽象化した表現に用いられます。点を頂点(node, vertex)、頂点と頂点の間の線を辺(edge)といいます。

ここでは頂点を駅、辺を路線と考えてみましょう。

「同じ駅は2度通らずに（つまり各駅をただ1度だけ通って）、すべての駅を巡る経路を見つける問題」を考えてみます。このような経路は複数考えられます。

以下にハミルトン路の1つの例を赤線で示しています。a → b → d → f → e → c の順に、どの駅もちょうど1度ずつ通っています。

また、旅だとすると出発地点に戻りたいので、出発駅を除いて同じ駅は2度通らずに、すべての駅を巡って出発点に戻る経路を見つける問題もあります。

ハミルトン閉路の例を以下に示しました。先ほどのハミルトン路の終点 c から出発点 a へ戻る辺を加えたものです。

さて、鉄道マニアの中にはすべての駅ではなくて、すべての路線を制覇したいという場合もあると思います。この場合は、「同じ路線は1度だけしか通らずに、すべての路線を巡る経路を見つける問題」を解くことになります。駅は何度通過しても構いません。

以下にオイラー路の例を示しています。ハミルトン路のように単純に経路を示すことが難しいので、辺に番号と矢印をつけて経路を巡る順番を示しています。辺の番号の順番にたどると一筆書きできることがわかると思います。駅 b, c, e は2度ずつ通っていますが、どの路線もちょうど1度だけ通っています。

ハミルトン路とオイラー路の違いを表にまとめておきます。

ここで、練習問題です。以下の3つのグラフについて、ハミルトン路とオイラー路があるかどうかを、それぞれ調べてみてください。あるなら実際に1つ見つけてください。

グラフが与えられたとき、

最悪時間計算量の観点からは、どちらが計算量の大きい問題でしょう。少し立ち止まって考えてみてください。入力のサイズとして、頂点の数や辺の数を用います。先程の例のような小さな規模の問題では、ハミルトン路もオイラー路も見つける手間はほとんど変わらなかったかもしれません。

生物の遺伝情報であるゲノム配列を解読する作業は、問題の定式化のしかたによって、ハミルトン路問題にもオイラー路問題にもなります。短い断片(数百文字程度)を大量に読み取るシーケンサーのデータでは、オイラー路問題として解く定式化が広く使われています。

ここでは、非常に単純化した形でこの問題を説明します（生命科学科の学生には単純化しすぎ！と怒られそうですが、ご容赦ください）。

「めかぶどうめだか」という文字列が解読したいゲノム配列だとします(実際のDNAの配列は、A, C, G, Tの4種類の文字からなる非常に長い記号列です)。ゲノム配列は実際にはとても長い配列なので一度に解読することはできません。そこでまず元のゲノム配列を複数本に複製して、そのゲノム配列を短い断片に切りわけます。

ぶつ切りにした結果、以下のような文字の断片が得られたとします。1行が複製1本分で、空白は断片が得られなかった部分です。

この断片から前後が重なっている文字を見つけ出してつなぎ合わせて、元の長い文字列を再構成する作業をゲノムアセンブリといいます。同じ断片(ここでは「めかぶ」)が複数得られることもありますが、1つにまとめて考えます。たとえば、「めかぶ」と「ぶどう」の「ぶ」が重なっているので、この2つをつなげて「めかぶどう」のようにつなげます。

ここでは、説明を簡単にするために前後が重なっている部分は1文字だけにしています。（実用的にはこれでは関係ないものまでつながってしまう可能性があるため、実際には複数の連続した文字列がオーバーラップする部分をつなげます。）

ここでは話を単純にするために重なりを1文字にしたので、すべての単語を1度ずつ用いてしりとりを完成させる問題になります(「ん」で終わると負け、といったルールは考えません)。この問題は頂点（ノード）に単語を配置して、しりとりとして繋がる可能性のある頂点間を矢印のついた辺でつなぐと下図のようなグラフができます。このグラフからハミルトン路を見つけることができれば、全単語をもちいたしりとり問題を解いたことになります。ただし、辺には矢印がついていて一方通行です。一般の有向ハミルトン路問題にも多項式時間の解法は知られていません。ただし、ここでしりとりから作った特殊なグラフには、後述の別の解き方があります。

実際にハミルトン路を求めてみると、

となり、しりとりが完成することがわかります。

実は、このしりとり問題をハミルトン路問題に帰着させるのは、牛刀をもって鶏を割くようなもので、ハミルトン路問題の表現力を無駄遣いしています。難しい問題を解く強力な手法を、簡単な問題に使うのはもったいないのです。一般のハミルトン路を探索するアルゴリズムを使わずに解ける問題を、わざわざそのように定式化してしまっているということです。

すべての単語を用いたしりとり問題は（一方通行の道から構成される）オイラー路問題で表現できます。頂点ではなく辺が単語を表すように、単語ではなく文字を頂点にします。つまり、単語「めかぶ」を、先頭の文字「め」から末尾の文字「ぶ」へ向かう矢印（辺）に置き換えるのです。また、しりとりでは両端に位置する文字以外はしりとりに関係ないので省きます。帰着方法の詳細は書きませんが、以下の図をみてイメージをつかんでください。

このグラフ上でオイラー路をみつければ、それがすべての単語を用いたしりとりになっていることがわかると思います。め → ぶ → う → め → か と矢印をたどると、めかぶ → ぶどう → うめ → めだか の順に単語が並びます。一方通行の辺からなるグラフでは、次数の代わりに各頂点に入る辺と出る辺の数を比べることで、オイラー路の有無を同じように判定できます(章末の練習問題8で扱います)。このように、元の文字列を再構成するためにオイラー路問題を解くグラフを、この形のグラフを1946年に考案したオランダの数学者ド・ブルインにちなんで、de Bruijn グラフ（ド・ブルイングラフ）と呼びます。

この単純化したモデルでは、一般のハミルトン路探索を使うより、オイラー路として解くほうが効率的です。ただし、実際のゲノムアセンブリには読み取り誤りや反復配列などがあり、すべてが一筆書きだけで解決するわけではありません。

実際のゲノムアセンブリの作業では非常に巨大な de Bruijn グラフができます。このグラフをメモリ上で小さく表現したまま（簡潔de Bruijnグラフ）経路をたどるアルゴリズムが開発されています。新型コロナウイルス（SARS-CoV-2）で最初期に公開された全ゲノム配列も、簡潔de Bruijnグラフを用いる解析ソフトMEGAHITで組み立てたものが使われました(論文では別のソフトTrinityも併用しています)。2020年1月に公開されたこの配列が、mRNAワクチンを設計する出発点になりました。現在のワクチン開発や創薬の背後には、さまざまなアルゴリズムの貢献があります。

出典：Wu et al., A new coronavirus associated with human respiratory disease in China, Nature 579 (2020)。

理化学研究所と富士通が共同開発したスーパーコンピューター富岳は2020年から2年間、計算速度の世界ランキングで1位となりました（現在は1位ではなくなってしまいましたが…）。性能の指標については細かい話もあるのですが、ここでは「富岳は1秒間に約44京回の計算ができる」を目安にしましょう。44京は \(4.4\times 10^{17}\) ですから、富岳の約230倍速い仮想的な計算速度、つまり1秒間に \(10^{20}\) 回計算ができるコンピューターを想定して、計算時間の比較をしてみましょう。

表の「-」は、値が大きすぎるため省略した欄です。

\(n^2\) と \(2^n\) や \(n!\) との間には、入力サイズの変化に対する計算時間の増加について、はっきりとした違いがあります。\(2^n\) のような指数的な増加は、わずかな入力サイズの増加が、爆発的な計算時間の増加につながり、計算量を改善することが非常に困難であることが想像できると思います。スーパーコンピューターやハードウェアの目覚ましい発展ですら焼け石に水と感じるほど、指数的な計算時間の増加は爆発的なのです。

そこで、\(\text O(n)\) や \(\text O(n^2)\) のように、上界が多項式でおさえられる時間計算量を、多項式時間と呼び、比較的、太刀打ちしやすい時間計算量であると考えます。多項式とは、一般的に、\(a_k n^k + a_{k-1} n^{k-1} + \cdots + a_2 n^2 + a_1 n + a_0\) の形をした式のことですが、ビッグオー表記では、次数が最大の項のみを考慮します。また、\(\text O(n \log n)\) の場合、厳密には多項式ではありませんが、多項式時間で抑えられる時間計算量ということで、多項式時間とみなします。

Yes/Noで答える決定問題のうち、最悪時間計算量が入力の長さの多項式でおさえられるアルゴリズムをもつ問題すべての集まり（このような集まりをクラスといいます）をP問題とよびます（多項式時間のことを英語で Polynomial Time というため）。

整列やオイラー路の構成は、多項式時間で解ける探索・出力の問題です。Pは厳密には決定問題のクラスなので、例えば「オイラー路は存在するか」という形にしてPへの所属を述べます。オイラー路の存在は、各頂点の次数を数えて連結かどうかを確かめるだけで判定できるので、この問題はPに属します。一方で、「ハミルトン路は存在するか」を判定する問題がP問題に含まれるかどうかは未解決問題です。多項式時間のアルゴリズムは見つかっておらず(すでに見たように、知られている上界は指数時間でした)、かといって「どんなアルゴリズムでも多項式時間では解けない」という下界の証明もないのです。

なお、多項式時間といっても \(\text O(n^{100})\) のような場合は、とても現実的な計算量とは言い難く、あくまでも多項式時間は理論上の1つの目安であることも念を押しておきます。

すでにみてきた整列問題や、ハミルトン路・オイラー路を見つける問題は、解くのが易しいか難しいかにかかわらず、いずれも解の候補が示されれば、それが本当に解になっているのかどうか検証することが簡単にできます。 整列問題では、与えられた並びの値を、隣り合う値が非減少順であることに加え、入力と同じ要素が同じ個数ずつ含まれていることも確認します。ハミルトン路問題では、解として示された経路をたどりながら、各頂点がちょうど1度ずつ現れ、連続する頂点の間に辺があることを確認します。オイラー路については、示された経路が、すべての辺を重複せずに含んでいることを確認します。いずれも、入力サイズに対して、多項式時間で検証できることは想像できると思います。

NPは、次の2つの条件を満たす検証の手続き(検証器)をもつ決定問題のクラスです。

ハミルトン路の存在判定なら、証拠は頂点の並び、検証器は「各頂点がちょうど1度ずつ現れ、隣り合う頂点の間に辺がある」ことを確かめる手続きです。ハミルトン路をもたないグラフでは、どんな並びを渡しても、この確認のどこかで必ず失敗します。

証拠を効率よく見つけられるとは限りません。NPの定義は、見つけ方は問わず、「見せてもらえれば確かめられる」ことだけを求めています。

NP問題のNPは、Nondeterministic Polynomial Time(非決定性多項式時間)の略です。NPはもともと、非決定性チューリングマシンという仮想的な計算機で多項式時間で解ける問題として定義されました。これは、分かれ道に来るたびに、あたかも正解につながる道を選べるかのように振る舞う機械です。そのとき選んだ道の列を証拠とみなすと、上の検証による定義と同じクラスになることが知られています。この章では、検証による定義を使います。なお、NPは「多項式時間ではない(Non-Polynomial)」の略ではありません。次の節で見るとおり、Pの問題もすべてNPに含まれます。

ある問題が別の問題と「どれくらい似ているか」「どちらが難しいか」を調べるための強力な道具が「多項式時間還元」です。

難しそうな用語に聞こえるかもしれませんが、考え方は「翻訳」に似ています。たとえば、日本語しか読めないけれど、英語で書かれた重要な文章を理解したいとします。そのときは、おそらく翻訳ツールを使って、英語の文章を日本語に「翻訳」するでしょう。翻訳さえできれば、日本語を読む能力を使って、元の英語の文章の意味を理解できます。

多項式時間還元もこれと同じ発想です。難しさを比べたい問題Aと問題Bがあるとき、問題Bの入力を問題Aの入力へと「翻訳(還元)」します。もしこの翻訳が高速(多項式時間)にできるなら、次のことが言えます。

この「難しさの比較」が還元の要点です。

問題Bをある問題Aに帰着させるというのは、つまりは、問題Bに与える入力を、問題Aの入力に変換して、問題Aを解くということです。しかし、変換にどれだけ時間をかけてもいいのであれば、そこで、本質的な計算をしてしまっていることになりますので、問題の変換時間にも多項式時間という制約を与えます。また、問題A,Bともに決定問題の場合は出力がYes/Noで与えられますので、出力側の変換は不要で、そのまま問題Aの出力が問題Bの出力として使えます。

以下の図は決定問題（答えがYes/Noで答えられる問題）における多項式時間還元のイメージです。還元に必要なのは入力の変換だけであり、具体的に問題A,Bを解くアルゴリズムを示す必要はないことに注意してください。問題Bを問題Aに多項式時間還元可能であるとき、\(B\preceq_P A\) と表記します。\(P\) は多項式時間のPであり、\(\preceq\) は問題の難易度に関する順序関係を示しています。

還元の「向き」と難しさの関係をパイプラインの形でまとめると、次の図のようになります。

たとえば、4人の客 a,b,c,d がいて、「aとb」,「aとc」,「cとd」,「bとd」がそれぞれ知り合いの関係にあるとき、知人関係は左下の表のように表現できます（知人関係にある欄に「✔」が記入されています）。このとき、右下の図のように円卓に座れば隣には知人しかいないことがわかります。

さて、下のグラフについてハミルトン閉路の存在の有無を判定する問題を、円卓の席配置の存在の有無を判定する問題に変換してみましょう。

このグラフを知人関係を表す表に変換してみます。

辺でつながっている部分は、表では知人関係にあるとして「✔」を入れています。たとえば、頂点 a と b は辺で繋がっているので、表の a と b が行と列で交わる部分に「✔」を記入します。 このとき、知人だけが隣に来るような円卓の席の配置は複数あるかもしれませんが、少なくとも下の図が1つの解になっているのは、容易に確認できると思います。

このように円卓の席配置が存在するとき、かつそのときに限り、ハミルトン閉路も存在し、以下のようになります。

この入力の変換は、頂点の組 \(n^2\) 通りのそれぞれについて、辺があれば表に「✔」を書き写すだけです。したがって \(\text O(n^2)\) 時間、つまり多項式時間でできます。

以上の議論から、計算量の観点からはハミルトン閉路があるかどうかを判定する問題Bは、円卓の席配置があるかどうかを判定する問題Aよりも、簡単かまたは同等の難しさをもった問題であることがわかります。

そして、円卓問題は検算が容易であり、多項式時間でチェックできることはあきらかです。よって、円卓問題はNPに属する問題であることがわかります。

実はハミルトン閉路問題はNP完全であることが知られています。この事実をもちいると、これまでの議論から円卓問題もNP完全問題であるという論理的帰結に至ります。

上の例で示したことをまとめてみましょう。

解の検証(検算)が多項式時間でできることがわかっている問題Aがあるとします。つまり、問題AはNPに属する問題です。このとき、問題AがNP完全であることを証明するには次の2段階の手順を示せば良いことがわかります。

つまり、問題BはすでにNP問題のなかで最も難しい問題であるとわかっているので、同じくNPに属する問題Aも、多項式時間還元により問題Bと同じかそれ以上に難しい問題であることが判明すると、問題AはNP完全であることが結論づけられます。 (問題Aは解の検証が多項式時間でできるため、NPに属する問題であることに注意をしてください。) もし問題Aが多項式時間で解けるなら、還元により問題Bも、ひいてはすべてのNP問題が多項式時間で解けてしまいます。だからこそ問題Aは「NP問題の中で最も難しい問題の1つ」なのです。

ここで当然の疑問がわきます。多項式時間還元を用いてある問題がNP完全であることを示すには、最初の出発点となるNP完全問題が必要になります。それは、いったいどうやって得られたのでしょうか。歴史的には、はじめてNP完全であることが示された問題は、ブール代数の充足可能性問題（SAT問題）です。出発点となるこの1問だけは、還元元にできる既知のNP完全問題がありませんから、「NPに属するあらゆる問題から直接還元できる」ことを力ずくで示す必要がありました。その証明は後で扱うことにして、まずSAT問題そのものについて説明します。

この問題は出力がYes/Noの問題ですが、実際に変数への値の割り当てを見つける問題と変更しても計算量の議論はそれほど変わりません。実際にYesとなる証拠である変数の割り当てが示されると、検証は変数に示された値を代入して計算するだけですので、多項式時間で計算可能です。

SAT問題の例をみてみます。

真理値表を書くのが確実ですが、変数が5つありますので面倒です。 この論理式の値を1にする変数の割り当ては複数ありますが \(x=v=1\), \(w=0\) であれば、残りの変数の値はなんであってもよさそうです。よって、たとえば \(f(1,0,1,1,1)=1\) となります。よって、答えは Yes です。

別の論理式についても考えてみます。

この論理式については、\(g(x,y,z)=1\) となるような変数 \(x,y,z\) への値の割り当ては存在しないため、答えは No です。この例では変数が3つなので真理値表を書いてもそれほど手間ではありませんが、変数が \(n\) 個の場合、真理値表の行数は \(2^n\) になりますので、真理値表を使えば指数時間かかります。

ここで、「そもそも、なぜSAT問題がNP完全の『最初の石』になれたのか？」という疑問が湧くかもしれません。他のNP完全問題はSATからの還元で証明されるのに、SAT自身はどうしたのでしょうか。

これは1970年代初頭にクックとレヴィンが独立に証明した、計算量理論における画期的な成果です。その証明の概要はやや難解ですが、かいつまんで説明すると以下のようになります。

クック（1971年）とレヴィン（1973年発表）の独立な結果は、還元の連鎖の出発点になりました。クックの発表の翌年、1972年にはカープが、SATを含む21の問題の間で還元を示して、それらがNP完全であることを一気に示します。その中には、ハミルトン閉路に関する問題も含まれていました。ハミルトン路の存在判定も、ハミルトン閉路からの還元によってNP完全であることが示されます。この章でオイラー路と対比してきたハミルトン路の問題は、NP完全だったのです。還元を積み重ねてNP完全性を芋づる式に広げていく話は、第13章でくわしく扱います。

NPに属するすべての問題を多項式時間還元できる問題のクラスを、NP困難(NP-hard)といいます。つまり、NP困難に属する問題は、NP完全に属する問題と同等か、それ以上に難しい問題であると言えます。

これらのクラスの包含関係を、P≠NPの場合とP=NPの場合とで対比して描くと、以下のようになります。どちらの場合も、NPとNP困難の重なりがNP完全です(これは上の定義そのものです)。P≠NPの場合、NP完全問題はどれもPに属さないので、NP完全とPは重なりません。また、P≠NPなら、PにもNP完全にも属さないNPの問題が存在することも証明されています(ラドナーの定理、1975年)。素因数分解の判定版は、そのような問題の候補と考えられています。

NP問題の定義をあらためて見直してみましょう。NP問題とは「答えがYesであることの証拠(解候補)が与えられれば、それが正しいことを多項式時間で検証できる問題」のクラスでした。ハミルトン閉路問題であれば、閉路を1つ見せてもらい、それをたどって確認するだけで「たしかに存在する(Yes)」と納得できます。

この定義は、YesとNoを対称には扱っていないことに注意してください。答えがNoのとき、つまり「グラフにハミルトン閉路が存在しない」ことを、相手に短時間で納得させる証拠にはどのようなものがあるでしょうか。頂点の順列をすべて確かめてもらう方法では、証拠の検証だけで指数時間かかってしまいます。ハミルトン閉路が存在しないすべての入力に対して使える、多項式長の証拠と多項式時間の検証方法は知られていません。個別には、グラフが非連結など、簡単に非存在を示せる場合があります。

そこで、NPの定義のYesとNoを入れ替えたクラスを考えます。答えがNoである各入力には多項式長の「Noの証拠」があって多項式時間で検証でき、答えがYesである入力ではどんな証拠も受理されない、という決定問題のクラスをco-NP問題といいます。ある問題のYesとNoを入れ替えた問題を補問題とよぶと、co-NPとは「補問題がNPに属する問題」の集まりだと言うこともできます。たとえば「グラフにハミルトン閉路は存在しないか」という問題は、ハミルトン閉路の存在判定の補問題なのでco-NPに属します。答えがNoであること(つまり閉路が存在すること)は、閉路を1つ示せば確かめられるからです。

co-NPの代表例は、SAT問題の補問題である「与えられた論理式は充足可能でないか」を判定する問題(UNSAT)です。この問題の答えがNoであること、つまり式が充足可能であることは、式の値を1にする割り当てを1つ示せば多項式時間で検証できます。「与えられた論理式は恒真式か(どのような値の割り当てでも値が1になるか)」を判定する問題(TAUTOLOGY)も同様です。恒真式でないことは、式の値を0にする割り当てを1つ示せば検証できるので、この問題もco-NPに属します。ここでTAUTOLOGYの入力は任意の論理式とし、CNFだけには制限しません。UNSATやTAUTOLOGYは、SATがNPの中で最も難しい問題であるのと対をなして、co-NPの中で最も難しい問題(co-NP完全)であることが知られています。

Pに属する問題は、証拠に頼らなくても多項式時間で自力で答えを計算できます。この場合、検証する側は渡された証拠を見ずに自分で答えを計算すればよいので、Yesの側にもNoの側にも(空の)証拠で済む検証器が作れます。したがって、Pに属する問題はNPにもco-NPにも属し、

が成り立ちます。\(\text{NP}\cap\text{co-NP}\) は、YesとNoのどちら側にも短い証拠がある問題のクラスです。

このクラスは「Pに属しそうな問題の候補地」とみなされることがあります。象徴的な例が素数判定問題(与えられた自然数は素数か)です。素数でないことの証拠は約数を1つ示せばよく、素数であることにも短い証拠があることが1975年に示されていたため、素数判定は \(\text{NP}\cap\text{co-NP}\) に属することが知られていました。これは「Pに属するのではないか」という兆候と受け止められ、実際、2002年にAKSアルゴリズムという多項式時間アルゴリズムが発見されて、素数判定はPに属することが証明されました。一方、次の節で登場する素因数分解に対応する判定問題も \(\text{NP}\cap\text{co-NP}\) に属することが知られていますが、こちらがPに属するかどうかは未解決のままです。

P=NPか?と同じように、NP=co-NPか?も未解決問題です。ここでもNP完全問題が鍵を握ります。もしNP完全問題が1つでもco-NPに属することが示されれば、NPのすべての問題はその問題に多項式時間還元できるため、NP全体がco-NPに含まれることになり、さらに対称性からNP=co-NPが導かれます。多くの研究者はNP≠co-NPと予想していますから、裏を返すと「NP完全問題はco-NPには属さない」、つまり「SATには、充足不能であることの短い証拠は存在しない」と予想されていることになります。

NP≠co-NPと予想される場合のクラスの包含関係を図にすると、次のようになります。前節の図の左側(P≠NPの場合)に、co-NPを描き加えた形になっています。NP完全問題はco-NPと重ならず、co-NP完全問題はNPと重なりません。NP完全問題が1つでもco-NPに入ると、上で見たとおりNP=co-NPになってしまうからです。

NP≠co-NPが証明されると、P≠NPも直ちに従います。対偶で考えてみましょう。もしP=NPなら、NPに属するどの問題も多項式時間で解けることになります。そして、Pに属する問題はYesとNoを入れ替えてもPに属したままです(自力で答えを計算してから反転すればよいだけです)。したがって、P=NPならばNP=co-NPも成り立ちます。この対偶をとると「NP≠co-NPならばP≠NP」が得られます。つまり、NP≠co-NPはP≠NPよりも強い主張です。逆に、P≠NPからNP≠co-NPが従うかどうかはわかっていません。P≠NPでありながらNP=co-NPであるという可能性も、論理的にはまだ排除されていないのです。