計算困難性とP≠NP予想

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

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

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

以下にハミルトン路の1つの例を赤線で示しています。

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

ハミルトン閉路の例を以下に示しました。

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

以下にオイラー路の例を示しています。ハミルトン路のように単純に経路を示すことが難しいので、辺に番号と矢印をつけて経路を巡る順番を示しています。辺の番号の順番にたどると一筆書きできることがわかると思います。

ここで、練習問題です。以下の3つのグラフについて、ハミルトン路とオイラー路を見つける問題を、それぞれ解いてみてください。

以下のようになれば、ハミルトン路とオイラー路の問題は理解できていると思います。

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

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

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

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

「めかぶどうめだか」という文字列が解読したいゲノム配列だとします。(実際にはご存知のようにACGTの4つのアルファベットからなる非常に長い記号列)。ゲノム配列は実際にはとても長い配列なので一度に解読することはできません。そこでまず元のゲノム配列を複数本に複製して、そのゲノム配列を短い断片に切りわけます。

ぶつ切りにした結果以下のような文字の断片が得られたとします。

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

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

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

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

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

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

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

このグラフ上でオイラー路をみつければ、それがすべての単語を用いたしりとりになっていることがわかると思います。このように、元の文字列を再構成するためにオイラー路問題を解くためのグラフのことを、このグラフを考案したオランダの数学者にちなんで、de Bruijn グラフ（ド・ブルイングラフ）と呼びます。

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

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

理化学研究所と富士通が共同開発したスーパーコンピューター富岳は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問題に含まれるかどうかは未解決問題です。つまり、多項式時間を超えるような時間計算量の下界が知られていないのです（すでに見たように現在の時間計算量の上界は指数時間でした）。

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

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

NPは、Yesである各入力に対して、入力の長さの多項式以内の長さの証拠があり、それを多項式時間で検証できる決定問題のクラスです。Noである入力では、どんな証拠を渡しても検証器が受理しないことが必要です。証拠を効率よく見つけられるとは限りません。 （厳密には、解候補を2進法で表記したときに、入力サイズに対して多項式サイズで表すことができるという条件も必要ですが、ここでは詳細には立ち入りません。）

NP問題のNPは、Nondeterministic Polynomial Time が由来です。検証が容易というのは、厳密に非決定性チューリングマシンという計算モデル上で多項式時間で解ける問題として定式化されますが、これについてもこの授業では立ち入りません（非決定的=nondeterministic）。

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

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

多項式時間還元もこれと同じ発想です。難しさを比べたい問題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つの解になっているのは、容易に確認できると思います。

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

この入力の変換が多項式時間でできるかどうかは、きちんと細かい議論が必要なのですが、直感的には直接的な変換ですし、多項式時間であるのはほぼ自明であるとしてこの授業では説明を割愛します。

以上の議論から、計算量の観点からはハミルトン閉路があるかどうかを判定する問題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に属するすべての問題を多項式時間還元できる問題のクラスを、NP困難(NP-hard)といいます。つまり、NP困難に属する問題は、NP完全に属する問題と同等か、それ以上に難しい問題であると言えます。

これらのクラスの包含関係を、P≠NPの場合とP=NPの場合とで対比して描くと、以下のようになります。

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

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

そこで、NPの定義のYesとNoを入れ替えたクラスを考えます。「答えがNoであることの証拠が与えられれば、それを多項式時間で検証できる問題」のクラスをco-NP問題といいます。ある問題のYesとNoを入れ替えた問題を補問題とよぶと、co-NPとは「補問題がNPに属する問題」の集まりだと言うこともできます。

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が証明されると、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であるという可能性も、論理的にはまだ排除されていないのです。