非決定性チエーリング機械の厳密な領域階層定理

摘要

あらまし　テープ記号が0と1に制限された1テープ非決定性チエーリング機械の厳密な領域階層定理を導出 する・s2（n）を領域構成可能関数とし，s1（n）はs2（n）≧（1＋ε）（s1（n＋3）＋n）を満たす関数とする．ただし， ε＞0は，任意に小さい有理数とする．このとき，s1（れ）領域の1テープ2記号1ヘッド非決定性チューリング 機械に受理される言語のクラスは，s2（n）領域の同機械のクラスに，真に包含されていることを証明する．ここ で，s2（n）≠0（n）のときは，条件s2（n）≧（1＋ε）（s1（n＋3）＋n）は，s2（れ）≧（1＋e）ss1（n＋3）に置き換える ことができる・本階層定理から，s（n）がれの多項式のときは，（1＋ε）s（n）とs（n）の二つの領域計算量クラス の間に階層があることが分かる・また，s（n）＝2~nのときは，（8＋ε）s（n）とs（n）の間に階層がある．