計算と言語の理論

概要

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

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

この章で重視すること

• 正規表現、有限オートマトン、CFG、PDA、チューリング機械を計算能力の違いとして比較する
• 言語の受理と決定問題の関係をつなげて考える
• P/NP、NP 完全、帰着、停止性問題を「限界を見極める道具」として理解する
• コンパイラやアルゴリズム設計との接続を意識して読む

目次

1. 形式言語とは何か
2. アルファベット・文字列・言語
3. 正規表現
4. 有限オートマトン
5. DFA と NFA
6. 正規言語の限界
7. 文脈自由文法 CFG
8. プッシュダウンオートマトン PDA
9. 文脈自由言語の限界
10. チューリング機械
11. 言語階層と計算能力
12. コンパイラとの接続
13. なぜこの理論が必要か
14. 計算可能性とは何か
15. 決定問題と認識問題
16. 停止性問題
17. 帰着の考え方
18. 時間計算量クラス
19. P と NP
20. NP完全
21. NP困難
22. 近似・乱択・実用上の解き方
23. 空間計算量とその周辺
24. 理論と実務のつながり
25. 参考文献

形式言語とは何か

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

コンピュータ科学では、

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

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

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

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

形式言語では、

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

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

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

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

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

• ab
• aab
• bbb

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

空文字

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

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

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

正規表現

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

たとえば

• 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 を見つけた

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

状態とは何か

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

DFA と NFA

DFA

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

NFA

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

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

NFA がなぜ便利か

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

DFA がなぜ実装向きか

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

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

DFA と NFA の比較

正規言語の限界

正規言語では、

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

を自然には扱えません。

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

ポンピング補題の直感

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

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

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

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

文脈自由文法 CFG

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

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

のように書けます。

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

なぜ重要か

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

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

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

文法規則の読み方

たとえば

Expr -> Expr "+" Term | Term

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

導出と構文木

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

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

あいまいな文法

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

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

例

1 + 2 * 3

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

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

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

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

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

これにより、

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

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

直感

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

なぜスタックなのか

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

CFG と PDA の関係

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

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

文脈自由言語の限界

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 を持ちますが、チューリング機械は左右移動しかできません。それでも計算可能性を議論するには十分強い、という点が重要です。

言語階層と計算能力

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

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

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

Chomsky 階層の見取り図

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

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

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

コンパイラとの接続

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

• 字句解析: 正規表現と有限オートマトン
• 構文解析: CFG と PDA 的な考え方
• 意味解析: 形式言語だけでは足りず、型や名前解決が必要

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

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

ここは重要な境界です。

• 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 やスタックを持つモデルの方が自然です。

練習問題

問題1

次のうち、有限オートマトンで自然に扱いやすいものはどれか。

• メールアドレスの単純な形式検査
• 深く入れ子になった括弧列
• 変数が宣言済みかどうかの判定

問題2

a^n b^n が正規言語でない直感を、自分の言葉で説明してみてください。

問題3

次の判定は、どの段階で行うのが自然か。

• 識別子の形が正しい
• if 文の括弧や波括弧の対応が正しい
• x + true が不正

問題4

1 + 2 * 3 が曖昧になりうる理由を説明し、どのように曖昧さを減らすか答えてください。

練習問題の考え方

問題1 の考え方

• 単純な形式検査は有限オートマトン向き
• 深い入れ子は CFG や PDA 向き
• 宣言済み判定は意味解析向き

問題2 の考え方

有限オートマトンは a を何個見たかを無制限には覚えられないので、後半の b と厳密に対応づけるのが難しいです。

問題3 の考え方

• 字句解析
• 構文解析
• 意味解析

の3段階に対応づけて考えると整理しやすいです。

問題4 の考え方

演算子の優先順位と結合規則を文法やパーサのルールに埋め込むと、構文木を一意に決めやすくなります。

追加トピック

閉包性

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

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

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

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

最小 DFA の直感

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

LL と LR の理論的位置づけ

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

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

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

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

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

具体例をもう少し

例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)$ の違いを復習したいときは、アルゴリズムとデータ構造 の 計算量 が土台になります。

計算可能性とは何か

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

たとえば、

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

は計算可能です。

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

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

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

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

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

決定問題と認識問題

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

例:

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

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

認識問題

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

なぜ判定版を作るのか

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

例

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

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

停止性問題

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

• この入力で停止するか

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

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

直感

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

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

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

つまり、

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

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

Rice の定理への入口

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

帰着の考え方

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

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

使いどころ

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

帰着の直感

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

多項式時間帰着

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

帰着でよく起きる混乱

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

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

時間計算量クラス

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

多項式時間

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

指数時間

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

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

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

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

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

擬多項式時間

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

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

代表的な増え方の見方

P と NP

P

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

NP

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

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

よくある誤解

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

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

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

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

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

P と NP の関係

現在分かっているのは、

• $P \subseteq NP$

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

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

もし P = NP なら

理論的には、

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

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

NP完全

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 が中心になるのか

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

NP 完全性証明の流れ

NP困難

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

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

例:

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

判定版と最適化版の違い

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

近似乱択実用上の解き方

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

近似アルゴリズム

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

ヒューリスティクス

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

乱択アルゴリズム

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

問題制約の活用

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

FPT とパラメータ化

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

ソルバの実力

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

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

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

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

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

空間計算量とその周辺

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

• L
• NL
• PSPACE

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

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

PSPACE の直感

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

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

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

理論と実務のつながり

ソルバ設計

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

コンパイラ最適化

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

セキュリティ

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

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

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

モデル検査と検証

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

代表問題で見る地図

例題で見る整理

例1: 最短経路

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

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

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

例3: 停止性問題

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

練習問題

問題1

次のうち、最も自然に NP の説明として近いものはどれか。

• すぐ解ける問題
• 答え候補があればすぐ確かめられる問題
• 絶対に解けない問題

問題2

「問題 A を問題 B に多項式時間で帰着できる」とき、どちらの方が少なくとも難しいと考えるべきか説明してください。

問題3

次の問題を分類してみてください。

• 与えられたグラフが連結か
• 長さ K 以下の巡回路が存在するか
• 任意のプログラムが停止するか

問題4

NP 完全だと分かった問題に対して、実務ではどんな方向で対処できるか、2つ以上挙げてください。

練習問題の考え方

問題1 の考え方

NP は「解く速さ」ではなく、「Yes の証拠を多項式時間で検証できること」で捉えるとぶれにくいです。

問題2 の考え方

A を B に変換して B を解くことで A も解けるなら、B は少なくとも A と同程度には難しい側です。

問題3 の考え方

• 連結判定は P
• 巡回路判定は NP 完全の代表例
• 停止性問題は決定不能

という地図に戻すと整理できます。

問題4 の考え方

• 近似アルゴリズム
• ヒューリスティクス
• 入力制約の活用
• パラメータ化
• ソルバ利用

の方向が典型です。

追加トピック

co-NP

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

PSPACE と EXPTIME の直感

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

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

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

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

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

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

具体例をもう少し

例4: ナップサック問題

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

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

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

例6: 静的解析の限界

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

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

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

よくある誤解

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

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

まとめ

計算可能性と計算量は、解けるか、どれくらいの資源で解けるかを考えるための地図です。P/NP、帰着、決定不能性を通して、万能解法を期待してよい場所とそうでない場所を見分けられるようになります。