L versus PのReversal versus Accessへの還元

スポンサーリンク

概要

論文の詳細を見る
折り返し計算量は、時間・領域計算量とともに本質的な計算資源として研究されてきた。本研究では、計算において使われる領域の中で最大のアクセス回数として定義される、アクセス計算量という計算資源を導入する。これに対して、領域・折り返しの同時制約計算クラスと領域・アクセスの同時制約計算クラスが類似している構造をもつことを示す。一方で、折り返し計算量とアクセス計算量の違いがL versus P問題と本質的に関連していることを示す。さらに、折り返し計算量とアクセス計算量の違いについていくつかの結果を示す。
社団法人電子情報通信学会の論文
2006-04-19

著者

上野賢哉
東京大学大学院情報理工学系研究科コンピュータ科学専攻

関連論文

スポンサーリンク