非決定性チューリング機械の厳密な領域階層定理(情報・システム基礎)

スポンサーリンク

概要

論文の詳細を見る
テープ記号が0と1に制限された1テープ非決定性チューリング機械の厳密な領域階層定理を導出する.s_2(n)を領域構成可能関数とし,s_1(n)はs_2(n)≥(1+ε)(s_1(n+3)+n)を満たす関数とする.ただし,ε>0は,任意に小さい有理数とする.このとき,s_1(n)領域の1テープ2記号1ヘッド非決定性チューリング機械に受理される言語のクラスは,s_2(n)領域の同機械のクラスに,真に包含されていることを証明する.ここで,s_2(n)≠O(n)のときは,条件s_2(n)≥(1+ε)(s_1(n+3)+n)は,s_2(n)≥(1+ε)s_1(n+3)に置き換えることができる.本階層定理から,s(n)がnの多項式のときは,(1+ε)s(n)とs(n)の二つの領域計算量クラスの間に階層があることが分かる.また,s(n)=2^nのときは,(8+ε)s(n)とs(n)の間に階層がある.
2010-09-01

著者

関連論文

もっと見る

スポンサーリンク