決定性時間と非決定性時間の分割に関する一考察

山本 博章  野口 正一  

誌名
電子情報通信学会論文誌 D   Vol.J70-D   No.6   pp.1057-1064
発行日: 1987/06/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: オートマン・言語理論
キーワード: 


本文: PDF(714.6KB)
>>論文を購入


あらまし: 
最近,オルタネーションの概念を使って決定性時間と非決定性時間の違いに関する結果がいくつか示されている.本論文はこれに関するもので,次の結果を得る.(1)1≦j<2なる任意の有理数jに対し,1TC-Dtime(nj)Ntime,space(njn),(2)1≦j<3/2なる任意の有理数jに対し,Ntime(n)1TC-Dtime(nj),ここで,1TC-Dtime(nj)はカウンタをもつオフライン1テープDTMによって時間0(nj)内で受理される言語のクラスを表す.(1)の結果の系として,1≦j<2に対し,off-Dtime1(nj)Ntime(nj)を得る.従来の結果で最良のものは,j≦1.104である.また,(2)の結果に関連して,我々はKannanと同様な結果,Ntime(n)ITC-Dtime(n1.104)も得る.