Gside

計算理論とオートマトンについて

チューリングマシン

無限長のテープを左右に動くヘッドをもち、ヘッドはテープの内容を読み書きすることができます。

時間計算量とは計算が停止するまでのステップ数の最大値を、入力の長さnの関数として表したものです。

時間計算量をt(n)、kを自然数としたとき、\( t(n) = O(n^k) \) となるときにt(n)を多項式時間といいます。

時間計算量をt(n)、kを自然数としたとき、\( t(n) = O(k^n) \) となるときにt(n)を指数関数時間といいます。

n = 100, k = 2 とした場合の値を計算してみます。

O(n^k) = 100² = 10000
O(kⁿ) = 2¹⁰⁰ = 1267650600228229401496703205376

上記のように、指数関数時間が莫大な値になることが実感できると思います。

問題Aが問題Bに帰着されるとは、問題Aの回答が問題Bの回答に翻訳されるということです。例えば、三角形の面積を求める問題は、三角形の底辺と高さを求める問題に帰着されます。

翻訳を行う関数を帰着関数と呼びます。この帰着関数の計算時間が多項式時間の場合、AはBに多項式時間帰着できるといいます。

多項式時間で受理される易しい問題のことです。

証拠が与えられなければ多項式時間で解けない難しい問題のことです。証拠が与えられれば正しいかどうかを非決定性多項式チューリングマシンでも受理できる問題のことです。

それ自身がNPに属していて、全ての問題が多項式時間帰着される問題のことです。

NP問題と同等か、それ以上に難しい問題のことです。