計算量理論入門
河村彰星

第一日 問題と機械
この講義では，入力された文字列のうち何らかの条件に適うもののみを受理したいという形をした問題を扱います．つまり問題とは文字列の集合（計算理論では言語と呼びます）に他なりません．例えば十進法で素数を表す文字列 2，3，5，7，11，…からなる集合をprime としましょう．0，1，…，9 からなる与えられた文字列が言語 prime に属するか答えよ（素数性の判定）という問が，ここで扱う問題の一例です．もう一つ例を挙げると，

a，b からなる文字列のうち連続する三文字として aba を含むものの全体 aba は一つの言語です．こちらは prime よりも簡単に判断できそうな感じがします．
実際，与えられた文字列が aba に属するか知るには，「aba」がどこまで出たか注視しながら読み進めればよい．その手順は図 1 で表されます．図に描かれた四つの場所 q0 ，q1 ，q2 ，q3 を状態といいますが，どの状態からも a と b の矢印が出ておりますので（q3 から出る「a，b」は二本の矢印をまとめて記したものです），「始」と書かれた状態 q0 から始め，入力された文字列を読み進めつつ，各時点の文字に従って矢印を辿ることにします．
例えば入力 abbaabab を読むと状態が順に q0 ，q1 ，q2 ，q0 ，q1 ，q1 ，q2 ，q3 と遷移し，二重丸のついた状態 q3 に至ります．
この図 1 のような仕掛を有限状態機械といい，機械が文字列を読んだとき二重丸の状態で終ることを（その文字列を）受理するといいます．図 1 をよく見ると，この機械が abaを含む文字列を受理し，含まない文字列は受理しないことが納得されましょう．これを，始q0b
図1aq1baq2aa, bq3b

言語 aba を認識する有限状態機械．

右b, cqA

始右a, b, cq̃Aac右c左b q
Ba, b, c左右左q̃B左a, c

図 2

more-a を認識するチューリング機械．a を一つ c に書換えながら右端まで進むことと，bを一つ c に書換えながら左端まで進むことを繰返し，a か b の一方が尽きたと判ると停止する．

この機械が言語 aba を認識すると呼ぶことにします．
これは言語 aba が十分に「簡単」だからこそ可能なことでした．有限状態機械によって認識される言語の全体を REG で表すことにしましょう．REG に属するのは，言語のうち aba のようにごく単純なものだけです．例えば a と b からなる文字列のうち a が b よりも多く現れるものからなる言語 more-a は，REG に属しないことが比較的容易に証明できます．有限個の状態では，a が b よりもどれだけ多いか正しく覚えられないのです．
もっと強力な計算の仕組を考えましょう．計算中に入力を読むだけでなく，自ら文字を書込む機能を加えた図 2 の機械は，more-a を認識します．先程は入力を右へ読み進めるだけでしたが，今度は（同じく左端の文字から始めますが）右にも左にも動くことができ，次に動く向きが矢の先に記されています（図 1 をこの書き方に合せるなら，すべての矢に「右」と書くことになります）．さらに例えば「c 右」は，現在の位置にある文字を c に書換えてから右へ進むことを表します（この c のように入力にない文字も使えます）．今度は一読みして終りではないので，入力文字列は左右に無限に長いテープ上に書かれており，何も書かれていない欄には （空白文字）が置かれていると考えることにします．図 2
では各状態から文字 a，b，c， を読んだときの動作を表す矢印が出ていますが，足りない所もあり，その場合（例えば状態 qB でを読んだ場合）には計算が停止（終了）します．

二重丸の状態で停止すれば受理です．停止せずいつまでも動き続ける場合（図 2 では起りませんが，あり得ることです）は受理していないとすることにしましょう．
この機械の仕組は 1930 年代にイギリスの数学者チューリング（A. Turing）が人の計算する様子を模して考案したものです．チューリング機械は，書込み機能のない機械に比べ，言語を認識する能力が高いと判りました．すなわち，チューリング機械によって認識される言語の全体を CE と書くと，REG ⊊ CE が成立ちます．このように問題の複雑さを，それがどのような機械で解けるかによって分類してゆくことが本講義のテーマです．

2

第二日 機械の万能性と限界
チューリング機械は高い能力をもち，あらゆる明確で実行可能な計算手順を表せると言われています．文字を一つ一つ読み書きするだけの簡素な機構でありながら，情報処理の本質を見事にとらえているのです．計算と呼べそうな仕組は他にもいろいろに考えられ，実際チューリングと同時代にクリーニ（S. Kleene）やチャーチ（A. Church）が考案した再帰函数やラムダ計算など，数や式に対する操作を抽象化した概念が登場しましたが，どうやらいかなる仕掛をこしらえてもチューリング機械と等価になる（その計算機構で認識できる言語は結局 CE に属する）らしい．およそ機械的な処理手順は皆チューリング機テーゼ械（やそれと等価な仕組）で書ける，というこの主張はチャーチとチューリングの定立と呼ばれます．勿論「機械的な処理」が厳密な概念でない以上，この主張は数学的に証明できる代物ではありませんが，広く受入れられています．このためチューリング機械そのものの定義の詳細は今後さほど重要ではありません．図 2 のごとく機械を正確に書いても読みにくいので，これからは手順が解りやすいように計算法を述べることにします．
例えば素数（を表す文字列）の言語 prime を認識する機械はどうでしょうか．与えられた正整数 X が素数か知りたければ，Y = 2，3，…，X − 1 について順に，X が Y の倍数か調べればよい．そのためには，テープ上（の X から少し離れた場所）に整数 Y を置くことにし，それを「2 から順に増やしてゆく」手順や，その各 Y について「X が Y で割り切れるか筆算のような方法で確かめる」手順を機械で実現することになります．後者の割り算の中では引き算を使いますが，それも機械の規則として書く．このように計算手順を部品ごとに組立ててゆくと，prime が CE に属することが確かめられます．
素数判定では Y を X − 1 まで調べれば終りですが，必ずしもこのようにあらかじめ終りの見える計算ばかりとは限りません．例えば次の問題 sr を考えます．入力として a とb からなる奇数個の文字列（を「,」で区切って並べたもの）u1 ,v1 ,u2 ,v2 , . . . ,um ,vm ,wが与えられます．これは各 i = 1，2，…，m について「文字列中に現れる ui を一つ vi に書換える」という操作ができることを表します．文字列 w をうまく書換えて空文字列（長さ 0 の文字列）に到達できるか問う問題が sr です（どの操作を何度使ってもよい）．例えば aa,bbb,aba,a,bb,,aababab は，次の書換え列が存在するため，sr に属します．
aba を

aba を

aa をbb を

bb をaにaにbbb に

空文字列に

空文字列に

aababab −−−→ aabab −−−→ aab −−−→ bbbb −−−−−−→ bb −−−−−−→（空文字列）
この問題 sr は，aba や more-a よりは難しそうですが，やはり CE に属します．もし空文字列へ到達可能なら，操作の施し方をすべて（見落しのないように然るべき順番で）実際に試してゆけばいずれ見つかるからです．このやり方では，sr に属しない入力が与えられた場合いつ諦めてよいやら知れず延々と動き続けることになりますが，それで構いま3

（空文字列）

0

100

01

10

11 000 · · ·x（空文字列）○××○×○×0×

○

○×××

○

1×××××××

00○×××○○×01○×○×○××××○

○×○

×..
.

図3M···

M ,x が eval に属するか否かを記した表（機械 M が入力 x を受理するとき○，しないとき×）．対角線上の成分を反転して定めた下段の行に一致する行は存在しない．

せん．言語を認識するというのは，その言語に属する文字列が入力されたら必ず受理すべし，しかし属しない文字列なら停止せずとも良い（誤って受理するのは不可）という要求だったからです．なお必ず計算を終えて結論を下すことまで要求する場合は認識ではな
く判定という言葉を使います（認識のことを半判定ともいいます）．
かようにさまざまな計算を表せるチューリング機械ですが，何でも認識できるわけではありません．CE に属しない言語は次のように作れます．まず機械とは図 2 のような有限の設計図ですから文字列で表せます．ここでは 0 と 1 からなる文字列を入力とするチューリング機械を考えることとし，そのような機械をやはり 0 と 1 からなる文字列で表す方法を一つ定めておきます．さて，文字列を漏れなく一列に並べて縦軸と横軸に排した表を考え（図 3），縦軸の M と横軸の x にあたる位置には，文字列 M（が表す機械）が文字列x を受理するか否かを○×で書込みます．つまり M の行にある○×は機械 M の挙動（どの文字列を受理するか）を表します．ここで表の対角線上の成分の○×を反転して下段のごとく書き並べると，これは表中のどの行とも完全には一致しません．すなわちこの行で○のついた文字列からなる言語は，どの機械にも認識されないと判りました．
この証明（対角線論法と呼ばれます）で用いたのは，機械を有限の文字列で書けることだけです．そもそも言語を認識するとは，無数にあり得る入力すべてに有限の手立てで正解しようとする企てであり，それにはどうしても限界があるのです．
しかし機械が文字列で表せるのは便利なことでもあります．これまで「more-a を認識する機械」「prime を認識する機械」のように特定の問題を解く機械を考えてきましたが，コンピユータ実際の計算機は一台であらゆる用途に使えます．つまり，個々の問題を解くことは普通，4プログラム

その問題に専用の計算機を製造することによってではなく，問題に合せた 算 譜 を，汎用・万能の計算機に読ますことによって実現されます．これは理論的には，言語

eval = { M ,x | 機械 M は文字列 x を受理する }を認識する機械が存在する（eval が CE に属する）お蔭といえます．この機械は，二つの文字列（を「,」で繫いだもの）M ,x を受取ると，あたかも機械 M に入力 x を与えたかのごとく振舞うわけですから，まさに万能機械の役割を果しています．機械を表す文字列を解釈・実行すること自体が，チューリング機械で書ける機械的な作業なのです．

eval は CE に属しますが，先程の対角線論法により，その補集合 eval は CE に属しません．また，機械というのは局所的に文字の書換えを行っているだけですから，その動きを問う問題 eval は文字列の書換え問題 sr に似ており，この類似に着目すると sr も CEに属しないことが判ります．先程 sr を認識した方法では，sr を判定する（入力された文字列が sr に属しないことも確実に断定する）ことはできていないと申しましたが，それは計算法をいかに工夫しようとも不可能なのです．
第三日 時間と空間の制限
現実の計算の特徴がチューリング機械でとらえられるというチャーチとチューリング
メモリの定立は，計算量（計算にかかる時間や，計算に用いる記憶の量）に関しても成立ちます．
つまり，現実に短時間で実行できる計算法は，停止までに行う遷移の回数が少ない機械で表されるし，小さな記憶空間で実行できる計算法は，訪れるテープ上の欄の個数が少ない機械で表される（ことが経験的に知られている）のです．これらの量が機械の仕組の詳細にあまり依存しないという事実は，時間や空間の制限が，実際上の関心事であるばかりでなく，問題に内在する複雑さを測る本質的な尺度であることを示唆します．計算量の重要性は世の中で計算機が広く使われ始めた 1950〜60 年代に明らかになり，以来さかんに研究されるようになりました．
一日目に考えた，書込み機能のない有限状態機械は，チューリング機械に対し，入力をひと通り読むだけの時間しか許さない，あるいは記憶空間の使用を全く許さないという，厳しい制限を課したものといえます．計算量理論では主に，そこまで強くはない一定の制限の下で何が計算できるか，つまり REG と CE の間がどうなっているかを考えます．
計算量を測るときは，入力の大きさ（文字列の長さ）に応じてどう増大するかに着目します（図 4）．とりわけ計算効率の最も重要な分れ目と考えられているのは，時間が入力長の多項式に収まる（すなわち多項式 p が存在し，任意の長さ n の入力に対して機械がp（n）回以内の遷移で停止する）か否かです．多項式時間のチューリング機械によって認識5

入力の長さ n = 10

図 43050

100

1000

10000

n

1 秒以内

1 秒以内

1 秒以内

1 秒以内

1 秒以内

1 秒以内

n21 秒以内

1 秒以内

1 秒以内

1 秒以内

1 秒以内

1秒

3n

1 秒以内

1 秒以内

1 秒以内

1 秒以内

10 秒

2.8 時間n51 秒以内

1 秒以内

1 秒以内

1.7 分

116 日

3 万年

2n

1 秒以内

11 秒

130 日

4 百兆年

n!

1 秒以内

8 京年













多項式時間

一秒に 108 回（一億回）の処理ができる計算機で，長さ n の入力に対して n 回，n2 回，n3回，n5 回，2n 回，n! 回の処理を行うのにかかる時間．多項式時間でない計算法は，n が大きくなるにつれて急速に時間が増大し，実行することがほぼ不可能になる．

される言語全体を P で表します．また遷移の回数の代りに訪れた欄の個数を測ることにより，同様に多項式空間で認識できる言語の集合 PSPACE を定義します．P や PSPACEクラスのように一定の制限下で解ける問題を集めた集合を計算量 級 と呼びます．

P に属するのは，入力長と同程度の手間で解ける容易な問題です（長さ n の入力に対して n3 や n100 の手間を「同程度」というのは乱暴な話ですが，ここでは鷹揚な心でそう考えることにします）．対して PSPACE の問題は，記憶領域は入力長と同程度しか使いませんが，時間に制限はないので，入力の内容から生ずる長い変化の行く末を調べたり，組合せで作られる厖大な可能性を考え尽したりという，大変な手間を要するかもしれません．
三日目の講義では図 5 の包含関係を示し，各級に属する問題の例を扱います．
例えば言語 sr は文字列の書換えに関する問題でしたが，PSPACE には属しません．書
換えを施すうちに初めの文字列より長くなることもあり，限られた空間では調べ切れないのです．そうならぬよう，長さの増える書換え規則は認めない（入力に現れる「ui を viに書換える」という規則において必ず vi が ui と同じ長さ以下）とした問題 sr≥ を考えますと，これは PSPACE に属します．ただ，夥しい回数の書換えを要する可能性はまだありますから，P に属するかは判りません．これに対し，ui よりも vi が（一文字以上）短いとし，更に規則の施し方が一意であるという一定の合流性を満す場合に制限した問題 sr1>
は P に属します．書換えの度にどんどん短くなるのであれば，もとの文字列の長さと同程度の手間で調べ終えられるからです．このように，問題をどう限定するとどこまで容易になるのか，計算量級の言葉で整理できます．
素数の問題 prime は，先述の通り X 未満に X の約数があるか調べ尽せば判定できる
ので PSPACE に属しますが，この調べ方では時間がかかります．P に属するというには，

6

sr1>

aba

REGsr≥

srevalmore-aprimePPSPACEEXPsrevalCE

図 5 計算量級の包含関係と，本稿で扱った言語．但し P と PSPACE とが本当に異なるか，またPSPACE と EXP（指数時間で認識可能な言語全体）とが本当に異なるかは判っていない．

X を十進法で書いたときの桁数（約 log X ）の多項式程度の時間で済さないといけません．
それが可能なのかどうか，長らく未解決でしたが，大勢の人がさまざまな整数論の知識を持込んで挑んだ末，今世紀に入ってインドの研究者らが新たな計算法を発見し（AKS 素数判定法），prime が P に属することが示されました．
一方，問題が P に属しないことを示すには，頑張ったけれど速い計算法が見つかりませんでしたというのでは証明になりません．いかなる方法を用いても絶対に不可能と立証するのは難しいことです．じつは今日なお，PSPACE に属する問題のどれ一つとして，P に属しないと証明されたものはありません．図 5 の PSPACE は P よりも広く描いてありますが，本当に PSPACE ̸= P であることは示されていないのです．きっと異なるはずだと久しく予想されながら未だ決着を見ない級は他にも数多く，それらを分離する証明法を編み出すことは計算量理論数十年来の宿題となっています．
第四日 帰着と完全問題
或る問題 B を解くと判っている手順を，その中身を気にせずに，別の問題 A を解く手順の一部として利用することは，実際の問題解決でもよく行われます．計算量理論においても「仮に問題 B が解けるとして」話を進めると議論の助けになることがあります．Bの解決に係る困難はさて措き，他の部分は簡単なのか，相対的に考えるのです．
これは言語 B を神託として用いるチューリング機械による計算として理解できます．
この機械は，計算の途中で好きな文字列を指定し，それが B に属するか教えてもらうことができます．この B の判定に要する時間や空間は考えず，即座に答が（神から告げられるかのごとく）もたらされるとするのです．B を神託として A を認識する多項式時間の機械が存在するとき，A は B に帰着するといい，A ≤ B と書くことにします．
これは「もし仮に問題 B が（多項式時間・空間などの制限下で）解けたら A も解ける」ということですから，不等号の表すように，A の複雑さが B 以下であると解してよいで

7

しょう．二日目で sr が CE に属しないと判ったのも，eval ≤ sr という帰着によるものと見なせます．また P に属するか不明な問題どうしの間でも帰着関係が詳しく調べられています．A ≤ B ならば，A や B が P に属するか属しないか四通りのうち，A が属せずB が属するという可能性だけは除かれるわけです．
このような帰着に基づく複雑さの整理に特に役立つのが困難性の概念です．PSPACEに属するすべての言語 A について A ≤ B が成立つとき，B は PSPACE 困難であるといいます．この場合 B という問題は，PSPACE = P でない限り P に属しないわけですので，多項式時間で解けないことがかなり確実といえましょう．例えば先に PSPACE の問題の例として挙げた言語 sr≥ は，じつは PSPACE 困難でもあることが証明できます．こうなると sr≥ は PSPACE の中でも最大の複雑さをもつ代表的な問題の一つであり，これを以て sr≥ の複雑さは或る意味でぴたりと同定されたといえるでしょう．
他にも多くの級について，このような最難の問題（完全問題）が知られています．しかも機械や文字列に関するものだけでなく，論理学や最適化など多様な分野の問題が，計算量級に基づく複雑さの類型の中に位置づけられるのです．四日目の講義では幾つかの完全問題を取り上げ，各問題のいかなる側面がそれぞれの複雑さを孕んでいるのか考えます．
参考文献
計算量理論の定評ある入門書を幾つか挙げておきます．

• M. Sipser. Introduction to the Theory of Computation, 3rd edition. Cengage
Learning, 2012.
•［前掲書旧版邦訳］マイケル・シプサ著，太田和夫・田中圭介監訳，阿部正幸・植田広樹・藤岡淳・渡辺治訳『計算理論の基礎原著第 2 版』共立出版（平成 20 年）• 岩間一雄『アルゴリズム理論入門』朝倉書店（平成 26 年）• O. Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.

8