2024-03-28T21:27:31Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001138332023-11-17T02:17:36Z06504:07924:07925
中間的な複雑さをもつ問題のクラスについてOn a Class of Problems with Intermediate Complexityjpnhttp://id.nii.ac.jp/1001/00113855/Conference Paperhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=113833&item_no=1&attribute_id=1&file_no=1国文学研究料館 情報処理室国文学研究料館 情報処理室国文学研究料館 情報処理室戸田, 誠之助堀, 浩一安永, 尚志計算量理論の中心的課題は与えられた問題をその複雑さによって分類する事である。この目的を達成するため様々な問題のクラスが導入されそのクラスに関して完全となる問題が数多く示されている。一方、導入されたクラスが大まかであるため分類されずに残っている問題も多い。例えば、グラフ同型問題や無向グラフの到達可能性判定問題(UGAP)などである。この状況をUGAPについて述べると次のようになる。UGAPはNL(非決定性対数領域)に属するがNL完全であるかDL(決定性対数領域)に属するかは判っていない。一般には、そのどちらでもない、いわば、中間的複雑さをもつと予想されている。そこで本稿では、このような中間的複雑さをもつ問題を分類するためのクラスを特にDLとNLの間に導入しそのクラスが中間的であるという根拠を与える。更に、そのクラスに関して完全となる具体的な問題を示す。AN00349328全国大会講演論文集第33回基礎51521986-10-012015-01-19