決定性有限オートマトン

• $K$ = 状態の集合
• $Σ$ = 入力の集合
• $δ$ = 現在の状態状態 -> 入力 -> 新たな状態
• $q_0$ = 初期状態
• $F$ = 受理状態の集合

非決定性有限オートマトンは$δ = K -> Σ -> \{K\}$となっている. ε付きは入力が空白の入力を受け付ける.

正規言語

• 列の長さ: その列に含まれる記号の個数, 列xの長さを|x|と書く.また長さ0の列を空列と呼び, εで表す.
• 列xとyの連接とは, 列xの後ろにyをつなげた列のことでxyと書く.またxxを$x^2$と書くこともある.
• 列xの逆あるいは逆語とは, 列xを逆から並べた列のことで, $x^R$と書く.例えば$x = 110$のとき, $x^R = 011$である.
• $L = \{a, bb\}$のとき, $L^* = \{ε, a, bb, aa, bbbb, abb, bba, aaa, bbbbbb, aabb, abbbb, …\}$である.

チューリング機械

• $Q$ = 入力記号
• $Σ$ = 入力記号の集合
• $Γ$ = テープ記号の集合
• $δ$ = Q -> Γ -> (Q, Γ, {L, R})
• $q_0$ = 初期状態
• $F$ = 受理状態の集合
• $H$ = 停止状態の集合

オーダー記法

最高次の項の値だけを取り, 他と係数は無視する. 高々$n^4$の時は$O(n^4)$. 正の整数$c$と$n_0$が存在して全ての整数$n > n_0$に対して$f(n) <= cg(n)$であるとき, $f(n)= O(g(n))$と書く. $f(n) < cg(n)$であるとき$f(n) = o(g(n))$と書く. $O(n) + O(n^2) = O(n^2)$

P vs NP

クラスPの問題は多項式時間で判定可能. クラスNPの問題は多項式時間で判定不可能, 検証は可能. 多項式とは$n^k$の形を取るとき, $k$が定数のものを指す. 要するに変数で冪乗したら多項式ではない.

NP完全問題とその例

まず, クラスNP問題は判定問題であり, yes/noで答えられる問題が属します. また, クラスPに属さなくても, 有限時間で判定が出来ない問題, 例えば停止性問題などは多項式時間で検証が不可能なため, クラスNPには属しません.

NP完全問題とは

1. クラスNPに属する
2. 全てのクラスNPに属する問題から多項式時間で帰着(変換)可能

な問題を指します.

P問題はNP問題でもありますが, 2を満たさないためNP完全問題にはなりません.

2009年にHAL研究所が開発し, 任天堂が発売したニンテンドーDS向けの｢立体ピクロス｣というコンピュータ向けパズルゲームがあります.

これの解の存在判定はNP完全であることが第15回ゲームプログラミングワークショップの｢立体ピクロスは NP 完全｣という文献で示されています.

この文献はweb上に一般公開されています.

この証明は3SATからの帰着によってなされています.

ちなみにこの文献によると, 高さが1で普通数字・丸数字・四角数字を区別しない立体ピクロス, つまり簡単になった平面ピクロスの, 解の存在判定はクラスPで行えることが示されています.