回路計算量の下限の研究とその応用

1.唯一最短格子ベクトル問題を効率的に解く量子アルゴリズムの設計(築地).(1)唯一最短格子ベクトル問題を,各次元が多項式サイズの環で形成されるような多次元整数環上のサイモン問題に帰着させた.(2)このように一般化されたサイモン問題を,線形計画法の問題に帰着させて,既知のアルゴリズムにより,多項式時間でとけることを確認した.その際、一定の周期dを隠しているような量子状態の観測値と、一様ランダムなる観測値との間に、ある種の期待値に関する一定の差が存在することを確認した。(3)この結果を応用して、2面体群の隠れ部分群問題が量子多項式時間以内に解けることを証明した。2.相関データグラフがエラーを含むときに遺伝系統図を構築する問題がNP完全であることの証明(築地・陳).(1)相関データグラフがエラーを含むときに、遺伝系統図の次数が有限であれば,創刊データグラフからエラーが最小の遺伝系統図を再構築する問題はNP完全であることを証明した。3.有限オートマトンの等価変換と状態数解析(松浦)(1)入力記号が{0,1}で,かつnが奇数である場合に,α≦3n-3の範囲でn状態NFAで,それと等価なDFAが2^n-α状態有するものが存在することを示した。4.六角盤面上の一般三並べの先手必勝問題(松浦)(1)六角盤面上の一般三並べ問題において、4つまでのタイルから成る全ての図形に関して,全てのサイズの盤面に対して,負け型である場合,および,勝ち型である場合は手順の最小性を示した.

1.唯一最短格子ベクトル問題を効率的に解く量子アルゴリズムの設計(築地).(1)唯一最短格子ベクトル問題を,各次元が多項式サイズの環で形成されるような多次元整数環上のサイモン問題に帰着させた.(2)このように一般化されたサイモン問題を,線形計画法の問題に帰着させて,既知のアルゴリズムにより,多項式時間でとけることを確認した.その際、一定の周期dを隠しているような量子状態の観測値と、一様ランダムなる観測値との間に、ある種の期待値に関する一定の差が存在することを確認した。(3)この結果を応用して、2面体群の隠れ部分群問題が量子多項式時間以内に解けることを証明した。2.相関データグラフがエラーを含むときに遺伝系統図を構築する問題がNP完全であることの証明(築地・陳).(1)相関データグラフがエラーを含むときに、遺伝系統図の次数が有限であれば,創刊データグラフからエラーが最小の遺伝系統図を再構築する問題はNP完全であることを証明した。3.有限オートマトンの等価変換と状態数解析(松浦)(1)入力記号が{0,1}で,かつnが奇数である場合に,α≦3n-3の範囲でn状態NFAで,それと等価なDFAが2^n-α状態有するものが存在することを示した。4.六角盤面上の一般三並べの先手必勝問題(松浦)(1)六角盤面上の一般三並べ問題において、4つまでのタイルから成る全ての図形に関して,全てのサイズの盤面に対して,負け型である場合,および,勝ち型である場合は手順の最小性を示した.