計算と言語の理論

目次

概要

形式言語・オートマトン・計算可能性・計算量をつなげる

この章では、文字列の規則を機械がどう認識するか、そもそも何が計算できるか、そして現実的な時間で解けるかをまとめて扱います。正規表現、有限オートマトン、文脈自由文法、チューリング機械、P/NPは別々の話ではなく、「計算の限界」を別の角度から見たものです。

要点

形式言語とオートマトンは「どんな入力を機械的に認識できるか」を、計算可能性と計算量は「何が解けて、どこから急に難しくなるか」を扱います。言語、機械、難しさを一本の流れで捉えると、理論同士のつながりが見えやすくなります。

この章で重視すること

形式言語とは何か

形式言語は、ある記号列の集合です。自然言語のような曖昧さを避け、機械的に扱えるようにしたものです。

コンピュータ科学では、

  • プログラミング言語の構文
  • 通信プロトコル
  • 入力フォーマット

などを形式言語として扱います。

なぜ自然言語ではなく形式言語が必要か

自然言語は便利ですが、曖昧さを含みます。たとえば「なるべく早く処理する」のような表現は、人間には通じても機械には通じません。

形式言語では、

  • 記号の集合
  • 並べ方の規則
  • 解釈の規則

を明示することで、機械的な扱いを可能にします。

アルファベット文字列言語

  • アルファベット: 使ってよい記号の集合
  • 文字列: 記号の並び
  • 言語: 文字列の集合

たとえばアルファベットが {a, b} なら、

  • ab
  • aab
  • bbb

は文字列です。これらのうち条件を満たすもの全部の集合が言語です。

空文字

何も文字を含まない文字列を 空文字 と呼び、しばしば ε で表します。空文字は「何もない」ですが、文字列としてはれっきとした一つの要素です。

言語を関数ではなく集合として見る

最初は「入力を処理する手続き」として考えがちですが、理論ではまず「どの文字列が属するか」という集合として見る方が重要です。これにより、異なる表現方法の等価性を比較できます。

flowchart LR Alpha["アルファベットaとb"] Str["文字列ab aab bbb"] Lang["条件を満たす文字列の集合"] Alpha --> Str --> Lang

正規表現

正規表現は、比較的単純なパターンを記述する方法です。

たとえば

  • a*
  • (ab|ba)
  • [0-9]+

のような形です。

正規表現が得意なこと

  • トークン分割
  • ログや文字列の検索
  • 単純な入力検査

正規表現が苦手なこと

入れ子構造です。たとえば括弧の対応のような「深さ」を持つ構造は、普通の正規表現では表せません。

正規表現の基本演算

理論的には、正規表現は主に次の3つの演算で組み立てられます。

  • 連接: ab
  • 選択: a | b
  • 反復: a*

この3つだけでかなり多くのパターンを表せます。

実務のregexと理論上の正規表現は少し違う

多くのプログラミング言語のregexエンジンには、

  • 後方参照
  • 先読み
  • 先読み否定

のような拡張があります。これらは便利ですが、理論上の「正規表現」の範囲を超えることがあります。

字句解析との関係

コンパイラの字句解析で正規表現が使われるのは、トークンの形が比較的局所的だからです。

  • 識別子
  • 数値
  • 演算子
  • 区切り記号

などは、深い入れ子を必要としません。

実際のコンパイラ側の見え方は、コンパイラ の 字句解析 をあわせて読むと、理論から実装への橋が見えやすくなります。

例

たとえば識別子を

[a-zA-Z_][a-zA-Z0-9_]*

と書くと、「先頭は英字かアンダースコア、その後は英数字かアンダースコアが0個以上」と読めます。これは有限個の状態で十分追えます。

有限オートマトン

有限オートマトンは、有限個の状態を持ち、入力を1文字ずつ読んで状態遷移する機械です。

重要なのは、「有限個の状態しか持てない」という点です。つまり、深い履歴を無限には覚えられません。

直感

  • 今どの状態にいるかだけを覚える
  • 入力を1文字読むたびに次の状態へ移る
  • 最後に受理状態ならOK

例

たとえば「ab を含む文字列」を認識するには、

  • まだ a を見ていない
  • a を見た
  • ab を見つけた

のような状態を持てば足ります。

flowchart LR S0["開始"] S1["aを見た"] S2["abを見つけた"] S0 -->|a| S1 S0 -->|b| S0 S1 -->|b| S2 S1 -->|a| S1 S2 -->|aまたはb| S2

状態とは何か

状態は「ここまで読んだ入力に関して、将来の判定に必要な要約」です。過去そのものを全部覚えるのではなく、未来の判定に必要な情報だけを有限個のケースへ圧縮しています。

DFAとNFA

DFA

Deterministic Finite Automaton。各状態と各入力に対して、次の状態が一つに決まります。

NFA

Nondeterministic Finite Automaton。複数の遷移候補を持てます。

理論的にはNFAとDFAの表現力は同じです。ただし変換すると状態数が大きく増えることがあります。

NFAがなぜ便利か

NFAは実装としてそのまま使うより、設計や証明に便利です。複数候補へ「同時に進める」と考えると、正規表現との対応が見やすくなります。

DFAがなぜ実装向きか

DFAは各入力に対する次状態が一意なので、実行時は非常に単純です。字句解析器の高速実装と相性が良い理由はここにあります。

このあたりは、コンパイラ実装で scanner や lexer generator がなぜ成り立つかの背景でもあります。

DFAとNFAの比較

項目 DFA NFA
次状態 一意 複数候補あり
実行時 単純 概念的には分岐を追う
設計のしやすさ やや厳密 正規表現から作りやすい
表現力 同じ 同じ

正規言語の限界

正規言語では、

  • 括弧の対応
  • a^n b^n のように個数を一致させる条件

を自然には扱えません。

理由は、有限オートマトンが「今まで何個見たか」を無制限には記録できないからです。

ポンピング補題の直感

正規言語の限界を示す古典的道具に ポンピング補題 があります。直感的には、状態数が有限なら、十分長い入力ではどこかで同じ状態を再訪するので、途中を繰り返しても受理性が変わらない、という考え方です。

この性質を使うと、a^n b^n のような言語が正規でないことを示せます。

なぜ a^n b^n が難しいのか

aaaabbbb を受理したいなら、a を何個見たかと b を何個見るべきかを対応づける必要があります。有限状態しかない機械では、この個数を無制限には覚えられません。

Myhill-Nerodeの考え方

正規言語の限界を見るもう一つの重要な道具がMyhill-Nerodeの定理です。細部まで証明を追わなくても、「未来の入力に対して区別しなければならない過去が有限個で済むか」という見方が役に立ちます。

有限オートマトンの状態は、ここまで読んだ文字列を、将来の判定に必要な情報へ要約したものです。もし、将来のどんなsuffixを付けるかによって無限に細かく区別しなければならないなら、有限個の状態では足りません。

flowchart LR P1["過去1"] P2["過去2"] S["将来の入力suffix"] R["受理 / 非受理が変わる"] P1 --> S --> R P2 --> S

この見方は、DFAの最小化ともつながります。将来の受理性に差がない状態はまとめられ、差がある状態は分けなければなりません。

文脈自由文法CFG

CFGは、入れ子構造を表現しやすい文法です。

S -> "(" S ")" S | ε

のように書けます。

これで括弧列の対応を表せます。

なぜ重要か

プログラミング言語の構文は、普通CFGでかなり自然に書けます。

  • 式
  • if文
  • while文
  • 関数定義

などは、再帰的な入れ子構造を持つからです。

文法規則の読み方

たとえば

Expr -> Expr "+" Term | Term

は、「Exprは Expr + Term でもよいし、Termだけでもよい」と読めます。こうした再帰が、式の入れ子を表現します。

導出と構文木

CFGでは、開始記号から規則を繰り返し適用して文字列を作ります。これを 導出 と呼びます。導出過程を木として見たものが構文木で、コンパイラ の構文解析と直接つながります。

実装側では、これが コンパイラ の 構文解析 や 抽象構文木AST に対応します。

flowchart TD S["S"] L1["("] Inner["S"] R1[")"] Tail["S"] S --> L1 S --> Inner S --> R1 S --> Tail

あいまいな文法

同じ文字列に対して複数の構文木が作れてしまう文法は、あいまい です。式の優先順位や dangling else は典型例です。

実用言語では、文法の書き方や優先順位規則で曖昧さを減らします。

例

1 + 2 * 3

は、優先順位規則がなければ

  • (1 + 2) * 3
  • 1 + (2 * 3)

のどちらにも読めます。コンパイラでは文法や優先順位表で一意に決めます。

正規文法とCFG

正規言語はCFGの一部としても表せます。右線形文法や左線形文法は、有限オートマトンと対応しやすい文法です。つまり、正規言語はCFGより弱いのではなく、CFGの中でも単純な形に制限された領域だと見られます。

構文木と抽象構文木

CFGから得られる構文木は、文法の規則をそのまま反映します。一方、実用コンパイラでよく使うASTは、余分な括弧や区切り記号を落とし、意味解析やコード生成に必要な構造だけを残します。

観点 構文木 AST
目的 文法規則の導出を表す 意味処理しやすい構造を表す
情報量 文法記号を多く含む 不要な記号を落とす
用途 理論・構文解析 コンパイラ内部表現

プッシュダウンオートマトンPDA

PDAは、有限オートマトンに スタック を足した機械です。

これにより、

  • 開き括弧を見たらpush
  • 閉じ括弧を見たらpop

のような処理ができ、入れ子構造を追えます。

直感

有限オートマトンは「状態だけ」でした。PDAはそこに「後入れ先出しの記憶」が1本増えた機械です。

なぜスタックなのか

関数呼び出し、括弧対応、再帰下降はどれも「最後に始まったものから先に閉じる」構造を持ちます。これはスタックと非常に相性が良いです。

CFGとPDAの関係

文脈自由言語は、CFGで書ける言語であると同時に、PDAで受理できる言語でもあります。これは「文法」と「機械」が同じクラスの言語を見ているという重要な対応です。

この対応を知っていると、パーサを単なる実装テクニックではなく、スタックを持つ認識器として見やすくなります。

flowchart LR CFG["CFG"] PDA["PDA"] CFL["文脈自由言語"] CFG --> CFL PDA --> CFL

文脈自由言語の限界

CFGやPDAでも万能ではありません。

たとえば

  • a^n b^n c^n

のように、複数系列の個数一致を同時に追う問題は扱いにくくなります。

スタック1本では足りない

a と b の対応だけならスタック1本で追えますが、さらに c まで同数かを同時に保証したいとき、記憶能力が足りなくなります。ここが文脈自由言語の限界を直感的に表しています。

何がつらいのか

a^n b^n c^n では、

  • a と b の対応
  • b と c の対応

を両方きれいに追う必要があります。スタック1本だと、片方に集中するともう片方の対応情報が崩れやすくなります。

チューリング機械

チューリング機械は、テープを読み書きしながら左右に移動する抽象機械です。

直感的には、

  • 無限に近い作業メモ
  • 読み書き可能
  • ヘッドを左右に動かせる

ので、一般的な計算モデルとみなせます。

なぜ重要か

チューリング機械そのものを実装するためではなく、「何が計算可能か」を定義するために重要です。

テープと有限制御

チューリング機械は、

  • 有限個の内部状態
  • 無限長のテープ
  • 読み書きヘッド

からなります。有限制御に、事実上無限の外部記憶を足したモデルだと考えると分かりやすいです。

ランダムアクセスでなくても強い

現代のコンピュータはRAMを持ちますが、チューリング機械は左右移動しかできません。それでも計算可能性を議論するには十分強い、という点が重要です。

flowchart LR Head["ヘッド"] Cell1["0"] Cell2["1"] Cell3["空白"] Cell4["1"] State["現在状態"] State --> Head Head --> Cell1 --> Cell2 --> Cell3 --> Cell4

言語階層と計算能力

大まかには次のように考えると分かりやすいです。

  • 正規言語: 有限状態で足りる
  • 文脈自由言語: スタック1本で足りる
  • より一般の言語: もっと強い記憶が必要
  • 再帰的可算言語: チューリング機械で扱える

つまり、機械が持てる記憶能力が増えるほど、扱える言語も増えます。

Chomsky階層の見取り図

厳密には階層はもっと細かいですが、初学者向けには次の見方が有効です。

  • Type 3: 正規言語
  • Type 2: 文脈自由言語
  • Type 1: 文脈依存言語
  • Type 0: 再帰的可算言語

これは単なる分類ではなく、「必要な記憶能力の増加」と対応しています。

階層 代表モデル 記憶能力の直感
Type 3 DFA NFA 有限状態だけ
Type 2 PDA スタック1本
Type 1 より強い機械 制約つきの大きな記憶
Type 0 TM 一般計算が可能

階層はなぜ真に広がるのか

直感的には、有限状態だけでは数え続けられず、スタック1本では複数系列の対応を同時に追いにくく、チューリング機械では読み書き可能な作業領域を持つため一般計算まで進めます。各階層で「記憶の形」が増えることが、扱える言語の広がりにつながります。

この章では厳密証明をすべて追うより、どのモデルがどの種類の記憶を持つかをまず意識すると理解しやすくなります。

コンパイラとの接続

この科目が コンパイラ とどうつながるかは重要です。

字句解析はどこまで正規表現でいけるか、構文解析でどこまで木を作れるか、意味解析から先は何が別問題か を分けて読むと、コンパイラ 全体の整理にも効きます。

どこまでが形式言語で、どこからが意味解析か

ここは重要な境界です。

  • if (x < y) { ... } の形が正しいかは構文の問題
  • x と y が比較可能かは意味の問題
  • 変数 x が宣言済みかも意味の問題

つまり、形式言語理論は強力ですが、プログラミング言語の全体はそれだけでは完結しません。

よくある誤解

「プログラミング言語は全部CFGで定義できる」と思いがちですが、実際には文脈依存の要素も多く、意味解析まで含めて初めて言語の全体像になります。

例題で見る整理

例1: 識別子

[a-zA-Z_][a-zA-Z0-9_]* のような識別子規則は正規表現で自然に書けるので、有限オートマトンで十分です。

例2: 括弧列

(()()) のような対応は深さを追う必要があるので、CFGやPDAが自然です。

例3: 型整合性

1 + true が不正だという判定は、正規言語でもCFGでもなく、意味解析の領域です。

例4: HTMLのような入れ子

開始タグと終了タグの対応を厳密に追いたいなら、単なる正規表現だけでは苦しくなります。入れ子深さを追う必要があるので、CFGやスタックを持つモデルの方が自然です。

形式言語の追加トピック

閉包性

形式言語のクラスでは、「ある操作に対して閉じているか」が重要です。

たとえば正規言語は次に対して閉じています。

  • 和
  • 連接
  • Kleene star
  • 補集合
  • 交差

これは、複数の単純な条件を組み合わせても、まだ有限オートマトンで扱えることを意味します。

文脈自由言語の閉包性

文脈自由言語は、和、連接、Kleene starには閉じています。一方で、交差や補集合には一般には閉じていません。ただし、正規言語との交差には閉じています。

この性質は、実務的にも少し顔を出します。たとえば「文脈自由な構文」に「字句的な正規制約」を組み合わせることは扱いやすいですが、文脈自由な条件同士を複雑に重ねると一気に難しくなります。

操作 正規言語 文脈自由言語
和 閉じている 閉じている
連接 閉じている 閉じている
Kleene star 閉じている 閉じている
交差 閉じている 一般には閉じていない
補集合 閉じている 一般には閉じていない

最小DFAの直感

同じ言語を認識するDFAは複数作れますが、不要な状態をまとめて最小化できることがあります。これは「異なる見た目の状態でも、将来の受理性に差がないなら区別しなくてよい」という発想です。

LLとLRの理論的位置づけ

実用上のパーサは、CFG全体を何でも楽に扱えるわけではありません。

  • LL: 先読みしながら上から展開する
  • LR: 下から畳み上げる

どちらもCFGを扱いますが、扱いやすい文法の形に差があります。ここが理論と実装の交差点です。

CYKと一般CFG

任意のCFGを扱う代表的な構文解析アルゴリズムにCYK法があります。文法をChomsky Normal Formに変換し、動的計画法で部分文字列がどの非終端記号から導出できるかを調べます。

実用コンパイラではLLやLRのような効率的なパーサが好まれますが、CYKは「CFGの一般的な解析はDPとして扱える」という理論的な見方を与えてくれます。

flowchart TD A["入力文字列"] B["短い部分文字列"] C["長い部分文字列"] D["開始記号で導出できるか"] A --> B --> C --> D

正規言語と文脈自由言語の見分け方のコツ

  • 深さが固定で、局所的な形だけ見ればよいなら正規言語寄り
  • 無制限の入れ子が必要なら文脈自由言語寄り
  • 型整合性や宣言済み判定が絡むなら意味解析寄り

形式言語の具体例

例5: if-else の曖昧さ

if a then if b then x else y

この else が内側の if に付くか、外側の if に付くかで構文木が変わります。これが dangling else の典型です。

例6: 字句解析では見えない意味

foo(bar)

この形だけでは、

  • foo が関数名か
  • bar が変数か型名か
  • 呼び出しが妥当か

までは分かりません。ここから先は意味解析の領域です。

形式言語パートの整理

形式言語とオートマトンは、どのような構造をどの計算モデルで扱えるかを整理する章です。正規表現、有限オートマトン、CFG、PDA、チューリング機械を並べてみると、理論とコンパイラ実装の橋が見えてきます。

計算可能性と計算量への橋渡し

ここから先は、「どんな言語をどんな機械が扱えるか」という話を、問題の難しさや決定可能性の話へつなげます。形式言語の受理という見方から、そのまま決定問題、計算量クラス、NP完全、決定不能性へ進めると、理論全体が一続きの地図として見えてきます。

なぜこの理論が必要か

アルゴリズムを学び始めると、「もっと速い方法があるか」を考えるようになります。しかし理論を進めると、次の2つの問いが現れます。

  1. そもそも機械的に解けるか
  2. 解けるとして、現実的な時間で解けるか

この2つを整理するのが、計算可能性と計算量理論です。

Big-Oの先にある問い

アルゴリズムとデータ構造 では、あるアルゴリズムの増え方を見ました。ここでは、そもそも

  • その問題に多項式時間アルゴリズムはありそうか
  • そもそも一般には決定できるのか

という、もう一段抽象度の高い問いを扱います。

計算量そのものの直感や、$O(n \log n)$ と $O(n^2)$ の違いを復習したいときは、アルゴリズムとデータ構造 の 計算量 が土台になります。

flowchart TD Q1["そもそも解けるか"] Q2["解けるならどれくらい速く解けるか"] Q3["速く解けないなら近似や制約活用は可能か"] Q1 --> Q2 --> Q3

計算可能性とは何か

計算可能性は、「ある問題に対して、必ず正しい答えを返す手続きが存在するか」を問います。

たとえば、

  • 整数の足し算
  • グラフの連結判定

は計算可能です。

一方で、一般には計算不可能な問題もあります。

計算可能と「実用的」は別

ここで大事なのは、計算可能であっても実用的とは限らないことです。

  • 計算可能だが非常に遅い
  • 計算可能だが入力サイズが少し増えるだけで破綻する

という問題はたくさんあります。

性質 意味
計算可能 理論上は必ず答えにたどり着ける
多項式時間 入力増加に比較的耐えやすい
実用的 定数倍や入力分布まで含めて現実に使える

決定問題と認識問題

理論では、問題をしばしば Yes/No で答える決定問題として扱います。

例:

  • 与えられたグラフにハミルトン閉路は存在するか
  • 与えられた論理式は充足可能か

Yes/Noにすると、問題同士の比較がしやすくなります。

認識問題

Yes/Noを返す代わりに、言語に属する入力を受理するかどうかで見る立場もあります。形式言語理論との接続を考えると、問題を「言語の受理」として扱う視点は非常に重要です。

なぜ判定版を作るのか

最適化問題は複雑に見えますが、まず「ある値以下で達成できるか」という判定版に落とすことで理論上の比較がしやすくなります。TSPの最適化版と判定版の関係は典型例です。

例

  • 最適化版: 最短の巡回路そのものを求める
  • 判定版: 長さ K 以下の巡回路が存在するか

理論では後者の方が比較しやすく、クラス分けにも向いています。

停止性問題

停止性問題は、チューリング機械またはプログラムに対して、

  • この入力で停止するか

を一般に判定できるか、という問題です。

結論は、一般にはできません。

直感

もし万能な停止判定器があると仮定すると、その判定器自身を入力として自己参照的な矛盾を作れてしまいます。これが決定不能性の代表例です。

何がそんなに衝撃的なのか

停止性問題の本質は、「十分に強力なプログラミング言語について、その全プログラムの挙動を完全自動で予測することはできない」という点です。

つまり、

  • バグを完全に自動発見する万能解析器
  • どんな最適化も常に安全か判定する万能器

のようなものは一般には作れません。

Riceの定理への入口

停止性問題を理解すると、次に見えてくるのが「プログラムの意味に関する非自明な性質は一般には決定不能」という方向です。これは静的解析の限界を考えるときに重要です。

Riceの定理

Riceの定理は、チューリング機械が認識する言語、つまりプログラムの意味に関する非自明な性質は一般には決定不能だ、という定理です。

ここで重要なのは「構文」ではなく「意味」に関する性質であることです。たとえば次のような問いは、十分一般的なプログラム全体に対しては決定不能になります。

  • このプログラムは空でない入力集合を受理するか
  • このプログラムは特定の文字列を出力することがあるか
  • このプログラムが計算する関数は常に0を返すか

静的解析との関係

Riceの定理は、静的解析が無意味だと言っているわけではありません。万能で完全な解析器は作れない、という限界を示しています。実務の静的解析器は、対象言語や性質を制限したり、偽陽性や偽陰性を許したりして役に立つ範囲を作ります。

解析の方向 特徴
soundに寄せる 見逃しを減らすが、偽陽性が増えやすい
completeに寄せる 誤警告を減らすが、見逃しが増えやすい
対象を制限する 実用範囲で強い保証を出しやすい
flowchart LR P["任意のプログラム"] H["停止判定器があると仮定"] C["自己参照で矛盾"] N["一般判定はできない"] P --> H --> C --> N

帰着の考え方

帰着は、「問題Aを解けたら問題Bも解ける」という変換です。

重要なのは、帰着は単なる書き換えではなく、難しさを別の問題へ運ぶ橋だという点です。

使いどころ

  • ある問題が難しいことを示す
  • 新しい問題を既知問題と比較する
  • 解法の発想を移す

帰着の直感

帰着は「AをBの形に埋め込む」ことです。もしBが簡単に解けるなら、Aも簡単に解けてしまいます。だから、Aが難しいと分かっていれば、Bも少なくとも同程度には難しいといえます。

多項式時間帰着

NP完全性では、変換そのものが多項式時間でできることが重要です。変換に指数時間がかかるなら、難しさの比較として意味が弱くなります。

帰着でよく起きる混乱

  • AからBに帰着できるとき、難しいのはB側
  • 向きを逆にすると結論が変わる

この向きの取り違えは非常に多いので注意が必要です。

flowchart LR A["問題A"] B["問題B"] Note["AをBに変換できる"] Hard["Bが簡単ならAも簡単"] A --> Note --> B --> Hard

many-one帰着とTuring帰着

帰着にも種類があります。NP完全性でよく使うのはmany-one reductionで、問題Aの入力を問題Bの入力へ1回変換し、Bの答えをそのままAの答えとして使います。

一方、Turing reductionは、Bを解くoracleを何度も呼び出してAを解くような考え方です。どちらも「難しさを比較する」道具ですが、使う場面と強さが違います。

帰着の作り方

帰着を作るときは、次を確認します。

  • 入力変換が多項式時間でできるか
  • Yes instanceがYes instanceへ写るか
  • No instanceがNo instanceへ写るか
  • 逆向きに証明していないか

特に最後の向きは重要です。難しさを示したい問題へ、既知の難しい問題を埋め込みます。

時間計算量クラス

入力サイズに対して、どの程度の計算資源が必要かで問題を分類します。

多項式時間

n2n^2 や n3n^3 のように、入力サイズの多項式で抑えられる時間です。理論上「現実的」と見なされることが多いですが、実際には定数倍や次数も重要です。

指数時間

2n2^n や n!n! のような増え方です。小さい入力では扱えても、すぐ現実的でなくなります。

なぜ多項式時間が特別視されるのか

多項式時間だから常に速いわけではありません。しかし、

  • 入力サイズが増えたときの悪化が比較的穏やか
  • 問題クラスとして安定している

ため、理論では一つの節目として扱われます。

擬多項式時間

入力値そのものに依存するアルゴリズムでは、見た目は多項式でもビット長に対してはそうでない場合があります。ナップサック問題の動的計画法は、この話題でよく出ます。

この「DPは使えるが理論上はまだ難しさが残る」という感覚は、アルゴリズムとデータ構造 の 動的計画法 とあわせるとつかみやすいです。

代表的な増え方の見方

クラス 例 印象
多項式時間 n2n^2, n3n^3 理論上扱いやすい
準多項式 2(logn)k2^{(\log n)^k} 中間的
指数時間 2n2^n すぐ苦しくなる
階乗時間 n!n! ごく小さい入力しか厳しい

PとNP

P

多項式時間で解ける決定問題のクラスです。

NP

答えがYesのとき、その証拠を多項式時間で検証できる問題のクラスです。

重要なのは、NPは「解けない問題」の集まりではないことです。Pに入る問題もNPに含まれます。

よくある誤解

  • Pは簡単、NPは難しい、ではない
  • NPはnon-polynomialの略ではない
  • NPの定義は「検証可能性」が中心

NPは「すぐに解ける」ではなく「すぐに確かめられる」

たとえば巡回セールスマン問題の判定版では、

  • 候補となる巡回路を誰かが持ってきたとき
  • その長さが条件以下か
  • 都市を一度ずつ通っているか

は多項式時間で検証できます。これがNPの直感です。

PとNPの関係

現在分かっているのは、

  • P⊆NPP \subseteq NP

であることです。問題はこれが真に小さい包含か、実は等しいのかです。これがP vs NP問題です。

flowchart TD NP["NP"] P["P"] NP --> P

ここでは包含のイメージだけを示しています。P が NP の内側にある、と読むのが直感です。

もしP = NPなら

理論的には、

  • 多くの探索・最適化問題
  • 形式検証
  • スケジューリング

が大きく変わります。ただし実際には次数や定数倍の問題もあるため、即座に全問題が実用化されるとは限りません。

NP完全

NP完全問題は、

問題です。

つまり、NPの中でも特に代表的に難しい問題群です。

代表例

  • SAT
  • 3-SAT
  • Hamiltonian cycle
  • CLIQUE
  • Vertex Cover
  • Traveling Salesman Problemの判定版

なぜ重要か

新しい問題がNP完全だと分かると、「一般にはうまい多項式時間アルゴリズムは期待しにくい」と判断できます。

NP完全性証明の典型パターン

  1. 問題がNPに属することを示す
  2. 既知のNP完全問題から多項式時間帰着する

この流れを何度も見ることで、難しさの運び方が分かってきます。

最初のNP完全問題

Cook-Levinの定理は、SATがNP完全であることを示しました。ここから3-SAT、CLIQUE、Vertex Coverなどへ難しさが次々に伝播していきます。

なぜSATが中心になるのか

論理式の充足可能性は、さまざまな組合せ問題を表現しやすいからです。多くの離散問題が「ある条件を満たす割り当ては存在するか」という形へ落とせます。

Cook-Levinの定理の直感

Cook-Levinの定理は、任意のNP問題の検証計算をSATの論理式として表せる、という発想です。チューリング機械の計算履歴を表に並べ、各時刻の状態、テープ内容、ヘッド位置が正しく遷移していることを論理式で制約します。

flowchart LR A["NP verifierの計算"] B["時刻ごとの計算履歴"] C["局所制約を論理式にする"] D["SAT instance"] A --> B --> C --> D

ポイントは、計算全体を巨大だが多項式サイズの論理式に変換できることです。これによりSATがNPの難しさを代表する問題になります。

代表的な帰着の連鎖

多くの教科書では、次のような流れでNP完全性を広げていきます。

flowchart LR SAT --> ThreeSAT["3-SAT"] ThreeSAT --> CLIQUE ThreeSAT --> VC["Vertex Cover"] VC --> HC["Hamiltonian Cycle"] HC --> TSP["TSP判定版"]

この連鎖を見ると、一つの基礎問題から多くの実問題へ難しさが伝わる様子が分かります。

NP完全性証明の流れ

flowchart LR SAT["既知のNP完全問題"] New["新しい問題"] InNP["まずNPに属することを示す"] Reduce["SATなどから帰着する"] Done["NP完全"] SAT --> Reduce --> New New --> InNP --> Done Reduce --> Done

NP困難

NP困難は、NP完全より広い概念です。NPに属する必要はありません。

最適化問題はしばしばNP困難です。

例:

  • 最短の巡回セールスマン経路を求める最適化版

判定版と最適化版の違い

判定版はYes/Noですが、最適化版は最良値そのものを求めます。理論ではまず判定版でNP完全性を示し、その後最適化版の難しさを議論することが多いです。

近似乱択実用上の解き方

現実ではNP完全だから終わり、ではありません。

近似アルゴリズム

最適ではないが、保証付きで十分よい解を返す。

ヒューリスティクス

保証は弱いが、現場ではよく効く。

乱択アルゴリズム

ランダム性を使って平均的にうまく解く。

問題制約の活用

実データは最悪ケースよりずっと素直なことが多いです。

FPTとパラメータ化

入力全体では難しくても、あるパラメータが小さいなら現実的に解けることがあります。これが固定パラメータtractableの考え方です。

ソルバの実力

SAT solverやSMT solverは、最悪ケース理論だけを見ると驚くほど強力です。ここから学べるのは、「理論上難しい」と「現実で役に立たない」は同じではない、ということです。

近似やヒューリスティクスを使う判断

  • 最適解が本当に必要か
  • 入力サイズはどれくらいか
  • 制約構造に偏りはあるか
  • 少し悪い解でも十分か

という問いで、厳密解法と実用解法を切り替えます。

実装寄りの見方では、アルゴリズムとデータ構造 の 乱択・近似・ヒューリスティクス がそのまま現場の発想に対応します。

空間計算量とその周辺

時間だけでなく、必要メモリ量でも問題を分類できます。

  • L
  • NL
  • PSPACE

などのクラスが知られています。

理論を深めると、時間と空間のトレードオフも重要になります。

PSPACEの直感

PSPACEは、多項式量の作業メモリで解ける問題のクラスです。時間は長くてもよいが、メモリは抑えられる、という見方ができます。

PSPACEとゲーム

PSPACE完全問題の直感をつかむには、二人ゲームや論理式の交互量化を見ると分かりやすいです。次のような形です。

exists x1 forall x2 exists x3 ... phi(x1, x2, x3, ...)

これは「先手がある手を選び、後手がどんな応答をしても、先手が次に勝てるか」というゲーム的な構造に似ています。全探索すると木は指数的に大きくなりますが、深さ方向に再帰すれば必要な作業メモリは多項式に抑えられることがあります。

QBF

Quantified Boolean Formula(QBF) はPSPACE完全の代表例です。SATがexistentialな割り当てを問うのに対して、QBFは exists と forall が交互に現れます。

SAT:

exists assignment: phi is true

QBF:

exists x, forall y, exists z: phi(x, y, z) is true

量化が入ることで、単なる「証拠を見ればすぐ確かめられる」より強い構造になります。

時間と空間のトレードオフ

ある問題では、メモリをたくさん使えば速くでき、メモリを節約すれば遅くなることがあります。実装上のキャッシュやDPも、この直感とつながっています。

理論と実務のつながり

ソルバ設計

SAT solver、SMT solver、MIP solverは、理論的には難しい問題を実用上かなり解きます。

コンパイラ最適化

レジスタ割付や命令スケジューリングにはNP困難な側面があります。そのため、厳密最適化ではなく実用ヒューリスティクスが使われます。

セキュリティ

暗号は「ある計算が難しい」ことを前提に立っています。

データベースとクエリ最適化

クエリ最適化や結合順序決定にも、組合せ爆発の側面があります。すべてを厳密最適にするのではなく、ヒューリスティクスやコストモデルを使う理由はここにあります。

モデル検査と検証

状態空間爆発は形式検証でも大きな問題です。理論上の難しさを知っていると、抽象化や部分探索がなぜ必要かが見えやすくなります。

代表問題で見る地図

問題 位置づけ コメント
連結判定 P グラフ探索で解ける
最短経路 P 実務で重要
SAT NP完全 出発点になりやすい
3-SAT NP完全 帰着でよく使う
TSP判定版 NP完全 巡回路存在判定
TSP最適化版 NP困難 最良値を求める
停止性問題 決定不能 一般判定不可

計算量の具体例

例1: 最短経路

グラフの最短経路は、通常は多項式時間で解けます。したがって「難しそうに見えるがPに入る問題」の代表例です。

例2: 巡回セールスマン問題

最短の巡回路を求める問題は非常に難しいですが、候補の巡回路が与えられたとき、それが条件以下か検証するのは比較的容易です。ここにNP的な直感があります。

例3: 停止性問題

どんなプログラムでも、その入力に対して停止するかを万能に判定することはできません。これは「遅い」ではなく、「一般には決められない」という種類の限界です。

計算複雑性の追加トピック

co-NP

No の証拠を多項式時間で検証しやすい問題群を考えると、co-NPという見方が出てきます。SATに対するUNSATの関係が典型です。

PSPACEとEXPTIMEの直感

  • PSPACE: メモリは抑えられるが時間は長くてもよい
  • EXPTIME: 指数時間かかってもよい

この差は、ゲーム木探索や論理の評価でよく出てきます。

時間階層定理と空間階層定理

計算資源を増やすと本当に解ける問題が増えるのか、という問いに答えるのが階層定理です。直感的には、より多くの時間や空間を許せば、以前の制限では解けなかった問題を解けるようになります。

この考え方は、PとEXPTIMEのようなクラスの違いを支える背景になります。

完全性は「そのクラスで特に代表的に難しい」こと

NP完全 と同様に、他のクラスでも PSPACE完全 などの概念があります。これは「そのクラスの難しさを代表する問題」だと考えると分かりやすいです。

平均的には速いが、最悪では厳しい

実務で重要なのは、最悪ケースの難しさと平均的な振る舞いを分けて考えることです。クイックソートやSAT solverの実感もこの差に近いです。

乱択と非一様計算

計算量理論では、決定的な計算だけでなく、乱択や回路も扱います。

BPP

BPPは、乱択を使って高い確率で正しい答えを返す多項式時間計算のクラスです。乱択アルゴリズムは、素数判定、近似、サンプリング、ハッシュなどで重要です。

乱択は「適当にやる」ことではありません。誤り確率を制御し、必要なら繰り返しで小さくできることが重要です。

回路計算量

回路計算量では、入力サイズごとに論理回路の大きさや深さを見ます。チューリング機械が逐次計算のモデルであるのに対し、回路は非一様な計算モデルとして使われます。

回路下界は、計算量理論の中でも非常に難しい領域です。P vs NPに近い大問題とも深く関係します。

なぜここまで広げるのか

乱択、回路、通信量、対話証明、量子計算などは、すべて「計算資源とは何か」を別の角度から見直す試みです。この章では入口だけに留めますが、理論計算機科学が単なる分類表ではなく、計算そのものを調べる広い分野であることが見えてきます。

実務で現れる具体例

例4: ナップサック問題

ナップサック問題はNP困難ですが、容量が小さいなら動的計画法がかなり効きます。ここで「理論上難しい」と「特定条件では実用的」が両立する例になります。

例5: ジョブスケジューリング

機械台数、締切、優先度、切替コストが入ると、現実のスケジューリングはすぐに組合せ爆発へ近づきます。そのため、厳密解法よりヒューリスティクスやMIPソルバが多用されます。

例6: 静的解析の限界

「このプログラムは絶対にバグがないか」を万能に判定するのは難しいです。そのため実務の静的解析器は、

  • 一部の性質に対象を絞る
  • 近似する
  • 偽陽性を許す

といった設計になります。

よくある誤解

  • NP完全なら絶対に解けない、ではない
  • Pなら実務で必ず速い、でもない
  • 決定不能なら部分的な解析も無意味、ではない
  • 理論は実務と無関係、でもない

理論が教えてくれるのは、「どこに万能解法を期待してはいけないか」と「どこで近似や制約活用に切り替えるべきか」です。

まとめ

計算と言語の理論は、入力をどの機械が認識できるか、そもそも何が計算できるか、そして現実的な資源で解けるかを一続きで見るための地図です。正規表現、有限オートマトン、CFG、PDA、チューリング機械は、記憶能力の違いとして並べるとつながって見えます。

その上で、停止性問題やRiceの定理は「万能な解析には限界がある」ことを、P/NP、NP完全、PSPACE、乱択、回路計算量は「解けるとしてもどれほど難しいか」を教えてくれます。実務では、ここで得た地図を使って、厳密解法、近似、ヒューリスティクス、ソルバ、制約の活用を切り替える判断がしやすくなります。

参考文献

公式・標準

講義・記事

書籍

解説・補助