このエントリーをはてなブックマークに追加 hatena-bookmark fb-like g-plusone
line-it
pocket
  • 作成日時:
  • 更新日時:

計算理論のテスト用ノート

決定性有限オートマトン

  • \(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で行えることが示されています.

このエントリーをはてなブックマークに追加 hatena-bookmark fb-like g-plusone
line-it
pocket