計算量クラスの理論的な分離と自動設計システムの評価への応用

本研究では,計算機の能力は計算時間やハードウェアサイズを増やせば真に上昇するという「計算量クラスの階層性」の理論的証明を目標としている.平成12年度は,以下の研究成果を得た.これらの成果は,自動設計システムの評価の為のテスト例題の生成に応用が期待できる.1.最も単純な並列処理システムであるセルオートマトンに対して,計算に並列性の概念を採り入れた交代性セルオートマトンが決定性(直列性)セルオートマトンよりも真に能力が高いという「計算量の階層性」を証明した.また,交代性による加速定理も証明した.これらの結果は,モルドバ共和国で2001年5月に開催される国際会議(International Conference on Machines, Computations and Universality)に採択が決定している.2.対数時間一様論理回路族に対して,段数t(n)と素子数z(n)を,それぞれ,(1+ο(1))t(n)logz(n)と(dt(n)+ψ(n)log^2z(n))(z(n))^2に増加すれば,真に計算能力が上昇するという階層定理を証明した.本結果は,クウェートで開催された国際会議(10th International Conference on computing and Information)にて公表した.会議録は2001年に出版される予定である.3.代表的な直列計算機モデルであるチューリング機械の時間・領域階層定理を証明した.本結果は,ブルガリアで開催された研究集会(9th International Colloquium on Numerical Analysis and Computer Science with Applications)にて招待講演として成果を発表した.

本研究では,計算機の能力は計算時間やハードウェアサイズを増やせば真に上昇するという「計算量クラスの階層性」の理論的証明を目標としている.平成12年度は,以下の研究成果を得た.これらの成果は,自動設計システムの評価の為のテスト例題の生成に応用が期待できる.1.最も単純な並列処理システムであるセルオートマトンに対して,計算に並列性の概念を採り入れた交代性セルオートマトンが決定性(直列性)セルオートマトンよりも真に能力が高いという「計算量の階層性」を証明した.また,交代性による加速定理も証明した.これらの結果は,モルドバ共和国で2001年5月に開催される国際会議(International Conference on Machines, Computations and Universality)に採択が決定している.2.対数時間一様論理回路族に対して,段数t(n)と素子数z(n)を,それぞれ,(1+ο(1))t(n)logz(n)と(dt(n)+ψ(n)log^2z(n))(z(n))^2に増加すれば,真に計算能力が上昇するという階層定理を証明した.本結果は,クウェートで開催された国際会議(10th International Conference on computing and Information)にて公表した.会議録は2001年に出版される予定である.3.代表的な直列計算機モデルであるチューリング機械の時間・領域階層定理を証明した.本結果は,ブルガリアで開催された研究集会(9th International Colloquium on Numerical Analysis and Computer Science with Applications)にて招待講演として成果を発表した.