小型デバイス上でのデータ処理アルゴリズムの使用メモリ領域の効率化

2022年度は7つの査読付き国際会議論文が採択され Springer 社から出版された。その他に、2つの査読付き論文が Elsevier 社の専門雑誌に掲載された。これらの論文で得られた研究成果の幾つかを簡単に記述する。対数領域計算量小型デバイスの数学的計算モデルを使い、デバイスの計算能力の分析を行った。こうした計算モデルの中でも特に、1970年代後半に提案された多項式状態数を持つ非一様性有限オートマトンの無限族モデル上の非決定性計算に着目し、初期状態から受理状態へ続く計算路が満たす条件の種類による計算量クラス間の新たな関係性を示すことで、相対的な計算能力を示した。2021年に発表した、書き換え回数制限のあるメモリ専用の保管テープを有する、決定性オートマトンを非決定性に拡張した計算モデルを今回新たに導入した。更に滝型論理回路と呼ぶ論理回路を定義し、前述の非決定性オートマトンとの同等性を証明し、国際会議で口頭発表を行った。国際会議論文は後日 Springer 社より出版された。「線形領域仮説」は、2017年に本研究者が提案した仮説で有り、2SAT3と呼ばれる充足可能な条件付き論理式の集合を多項式時間で認識するには、弱線形領域量では不十分であることを主張する。仮説の提案以降、既に5つの論文が出版されていて、その中の2つは2022年度中に国際会議で発表し、Springer社から論文が出版されている。その一つでは、2SAT3と同等の計算量を有する3つの新たな問題を提案し、2017年に導入された「短い還元性」の概念を用いて計算の複雑さの同等性を証明した。もう一つでは、細粒化時間計算量の研究の発展を模範として新たに細粒化領域量の概念を導入し、線形領域仮説の下で幾つかの決定問題の計算不可能性を証明した。

2022年度は7つの査読付き国際会議論文が採択され Springer 社から出版された。その他に、2つの査読付き論文が Elsevier 社の専門雑誌に掲載された。これらの論文で得られた研究成果の幾つかを簡単に記述する。対数領域計算量小型デバイスの数学的計算モデルを使い、デバイスの計算能力の分析を行った。こうした計算モデルの中でも特に、1970年代後半に提案された多項式状態数を持つ非一様性有限オートマトンの無限族モデル上の非決定性計算に着目し、初期状態から受理状態へ続く計算路が満たす条件の種類による計算量クラス間の新たな関係性を示すことで、相対的な計算能力を示した。2021年に発表した、書き換え回数制限のあるメモリ専用の保管テープを有する、決定性オートマトンを非決定性に拡張した計算モデルを今回新たに導入した。更に滝型論理回路と呼ぶ論理回路を定義し、前述の非決定性オートマトンとの同等性を証明し、国際会議で口頭発表を行った。国際会議論文は後日 Springer 社より出版された。「線形領域仮説」は、2017年に本研究者が提案した仮説で有り、2SAT3と呼ばれる充足可能な条件付き論理式の集合を多項式時間で認識するには、弱線形領域量では不十分であることを主張する。仮説の提案以降、既に5つの論文が出版されていて、その中の2つは2022年度中に国際会議で発表し、Springer社から論文が出版されている。その一つでは、2SAT3と同等の計算量を有する3つの新たな問題を提案し、2017年に導入された「短い還元性」の概念を用いて計算の複雑さの同等性を証明した。もう一つでは、細粒化時間計算量の研究の発展を模範として新たに細粒化領域量の概念を導入し、線形領域仮説の下で幾つかの決定問題の計算不可能性を証明した。