多項式時間計算可能関数
polynomial time computable function
関数$ f:\Sigma^\ast\rightarrow\Sigma^\astのこと
定義
多項式時間チューリングマシン$ Mが存在して、
任意の入力$ u\in \Sigma^\astで動作を開始し、テープに$ f(u)だけを設定して停止するならば、
$ fは多項式時間計算可能関数である
ざっくり言えば、
多項式時間チューリングマシン$ M、を計算する関数のことmrsekut.icon
ただのTMじゃなくて、多項式時間TMねmrsekut.icon
$ Mと同じ計算をする関数のことを、多項式時間計算可能関数と言う