はじめに

理論屋さんでもなく、理解力に自信のない自分が理解できるように、かなりかみ砕いた表現で書いているため、厳密性に欠けています。
ざっくりこんなものなんだな、こんな概念があるんだな程度に見ていただければ嬉しいです。

計算理論とは / 計算理論の論理体系

計算理論とは

コンピュータでどんな問題が解けるのか、どのくらいのコスト(時間・メモリ)で解けるのかを数学的頓知的に体系化した学問
計算可能性理論と計算量理論からなる
- 計算可能性理論→ある問題は理論上解けるのか解けないのかを分類する理論
- 計算量理論→ある問題をどのくらいの時間とメモリを使えば解けるのかを評価する

✅問題とは
入力が与えられたときに、それに対して答えを出すべきルールや要求のこと。
であるが、上記ではわかりにくいので…
⇒具体的にはFizzBuzz問題やナップサック問題ように形式的に定義された問題、業務における計算や判断など形式化すれば解決できる問題という理解でよい
✅業務における計算や判断など形式化すれば解決できる問題
一般的な業務で形式化できる課題例(問題)
　⇒効率的なスケジュールやシフトの作成
　⇒最適なスキルで分けるチームの編成

論理体系

今回はチューリングマシンと計算量クラスのP/NP/NP完全/NP困難について書きます

計算理論（Theory of Computation）
│
├─ 計算可能性理論（Computability Theory）
│   ├─ チューリングマシン（TM）
│   ├─ 決定可能 / 決定不能問題
│   ├─ 停止問題（Halting Problem）
│   ├─ λ計算 / μ帰納関数
│   └─ チューリング完全性（Turing Completeness）
│
└─ 計算複雑性理論（Computational Complexity Theory）
    ├─ 複雑性クラス
    │   ├─ P（多項式時間で解ける）
    │   ├─ NP（多項式時間で検証できる）
    │   ├─ NP完全（NP ∩ NP困難）
    │   ├─ NP困難（NPに還元できるがNPとは限らない）
    │   └─ PSPACE, EXP, etc.
    └─ 多項式時間帰着（Polynomial-Time Reduction）
        ├─ 問題間の困難性比較
        └─ 証明技法の中核となる概念
        など…

これらを知ってると何がうれしいのか / 何の役に立つのか / 何に使われているのか

理論的知識が特に必要ではないと感じているエンジニアがこれを知っていて何がうれしいのか
- 現状解ける/解けないの判断が理論的にできる
  
  後述するが、今のマシン性能や計算方法では解けない問題や理論上解決できない問題もある。
  知っていれば解けない問題に頭を悩ませる時間を減らすことができる
- アルゴリズム選定の限界がわかる
  
  最適解は求められないが近似解なら求められる問題もある
  その時に頑張って最適解を求めようとせず近似解のアルゴリズムを選ぶことができる
- 設計や技術選定の説得力が増す
  
  もっと最適な方法でなぜできないのかと言われたときに、この理論で裏付けて説明できる。
  また、自身ももっと最適にできる方法があるのでは…と悩まなくて済む
何に使われているのか
- RSAや楕円曲線暗号などはNP困難(後述)問題を前提にしてる

🌟チューリングマシン(TM)

チューリングマシン(TM)とは

イギリスの数学者・論理学者のアラン・チューリング（Alan Turing, 1912–1954）が考えた概念
- 現代のコンピュータの理論的基盤になっている
種類
- 決定性チューリングマシン(DTM)
- 非決定性チューリングマシン(NDTM)
TMが後述する計算量クラス(P/NP~)に関わっているのでなんとなく知っているとよい
以下のような構成を持つ理論上の計算機

要素	説明
無限のテープ	無限に続く記憶装置。各セルには記号(0,1,空白)を書き込める. (無限に続く1行のexcelのイメージ)
ヘッド (読み書き装置)	現在位置のセルの記号を読み書きし、左右に移動できる。
状態	マシンは内部状態（q0, q1, ..., qAccept, qRejectなど）を持ち、状態遷移によって動作する。
遷移関数 δ(デルタ)	現在の状態と読み取った記号に応じて、次の状態・書き込み・移動方向（L/R）を決定する。

イメージ図

決定性チューリングマシン(DTM)

特徴
- 各状態において、入力記号に対する次の動作が1つしかない(決まっているなどと表現)
- 入力に対して1本の処理経路のみをたどる
- 現実のコンピュータのモデルに近く、1つの手続きに従って処理を順番に進めるため、動作が予測可能
概念的な例

状態 q0 で「0」を読んだら、「1」に書き換えて、右に移動し、状態を q1 に変える

・ 状態q0: q1という現在のチューリングマシンの動作モード
・ テープ上の0を読んで、1に上書きする
・ 読み書きヘッドを右のセルに動かす
・ 内部状態をq1に更新し次の動作モードに遷移

以下で表す

δ(q0, 0) = (q1, 1, R)

具体的な例

迷路でゴールを目指す。
行き止まりになったらひとつ前の分岐点に戻って、別の道を選ぶ。

非決定性チューリングマシン(NDTM)

特徴
- NP問題（非決定性多項式時間の定義に重要
- 「ある解が存在するか？」を並列的に探索できる理想モデル
- 各状態・記号の組み合わせに対して、複数の選択肢（遷移先）が存在する
- マシンは、すべての選択肢を「同時に」探索して、どれか1つでも受理状態に到達すれば「受理」とする
例

状態q0で0読んだら「1に書き換えて、右に移動し、状態を q1 に変える」動作
または「0に書き換えて、左に移動し、状態を q2 に変える」動作を行う
δ(q0, 0) = {(q1, 1, R), (q2, 0, L)}

もう少しかみ砕く
- 非決定性とは
ある状態で複数の選択肢があり、どれを選ぶかが“決まっていない”状態
[決まっていない]とは次の動作が複数ある。
- 右または左に移動する
右or左と言う意味ではない
同時に(並列的に)右に行くパターンと左に行くパターンを試すという意味
q1,q2はそれぞれ同時に左右に移動する
- q1,q2が右右、左左には移動しないのか？
可能性として同時にすべての経路をたどるという概念
ゆえに必ず左右に移動するという考え方をする

具体的な例

迷路でゴールを目指す。
分岐点で自身が分身してそれぞれの道を行く。
それぞれの道でさらに分岐点にきたら、さらに分身してそれぞれの道を行く

非決定性チューリングマシン(NDTM)はどんどん計算量が増える

🌟計算量クラス(P/NP/BP完全/NP困難)

P/NP/BP完全/NP困難とは

計算の難しさをレベル別にしたもの
- Pが一番易しく、NP困難が一番難しい
N:Nondeterministic(非決定性)
P: Polynomial time(多項式時間)

用語

多項式時間
- アルゴリズムの実行時間が以下で表せるもの(kは定数)
  $$Q(n^k)$$
判定問題
- Yes or Noで決まる問題

P

特徴
- DTMで多項式時間以内に解ける
- 判定問題のみ

NP

特徴
- NDTMで多項式時間以内に解ける
- 判定問題のみ
- Pも含む
- NP完全でもPでもないものはNP中間問題と呼ばれる

NP完全

特徴
- NDTMで多項式時間以内に解ける
- NP問題の中で最も難しい問題の集合
- 難しさ→NP完全の問題が解けたら、NPの問題もその問題に多項式時間で変換できるくらい難しい
- NPかつNP困難の問題の集合
- 判定問題のみ
代表的な問題
- 充填問題（ナップサック問題）
- 巡回セールスマン問題（判定版）
- 3-SAT（充足可能性問題）
- グラフ彩色問題（3色彩色）

NP困難

特徴
- NDTMで多項式時間以内に解けるとは限らない
  - NPに属しているものは解けるが、属していない物に関しては必ずしも解けないし、絶対に解けない問題(停止性問題)も存在する
- 難しさ→NP困難の問題が解けたら、NPの問題もその問題に多項式時間で変換できるくらい難しい
- 判定問題に限らない
代表的な問題
- 停止性問題
- TSP

まとめ

計算量クラス	判定問題のみか	DTMで多項式時間で解けるか	NDTMで多項式時間で解けるか
P	○	○	○
NP	○	未解決(わかってない)	○
NP完全	○	未解決(わかってない)	○
NP困難	含まないこともある	今の技術・理論では効率よく多項式時間で解く方法がすべてのケースに対して見つかっていない	解けるとは限らない(停止性問題は解けない)