Development of the sublinear-time paradigm

本研究では研究代表者の提案している「劣線形時間パラダイム」を広く展開するための理論研究を行っている。２０２２年度の主な成果は以下の通りである。 (I) 定数・劣線形時間アルゴリズムをゲーム・パズルに拡張する研究を行っている。これまでいくつかの一般化ゲーム・パズルが定数時間検査可能であることを示してきたが、ボタン＆シザーズが定数時間検査不可能だとの予想を立てて証明を試みている。そして盤面を一次元に限った問題については定数時間検査不可能であることに対する我々の構築した証明が不完全であることを見つけた。具体的には、既に定数時間検査不可能であることが証明されている文字列問題を帰着することで行っているが、帰着の際に想定外のボタン消去手順が存在することを見落としていた。現在その証明を修正中である。 (II) 離散幾何学上の問題に対していくつか成果を上げた。まずDNA計算などに応用を持つ、ある種の折れ線の非交差平面埋め込み問題がNP完全であることを証明した。これはErik Demaine (MIT)らとの共同研究であり、国際会議CCCG2022のプロシーディングスに掲載された。他に多面体の全ての面を通る測地路であるFGG路(Face-Guard Geodesic Path)という概念を提示し、それを持つ多面体の特徴づけを行った。具体的には任意の四面体にはFGG路が存在するが、正四面体以外の正多面体にはFGG路は存在しない事、三角柱にFGG路の存在する必要十分条件などを明らかにした。また、数字の配置が均衡しているn面体ダイスの問題などに関する研究も行い、それらを国際会議JCDCG^3 2022で発表し、論文を投稿した。現在査読中である。

本研究では研究代表者の提案している「劣線形時間パラダイム」を広く展開するための理論研究を行っている。２０２２年度の主な成果は以下の通りである。 (I) 定数・劣線形時間アルゴリズムをゲーム・パズルに拡張する研究を行っている。これまでいくつかの一般化ゲーム・パズルが定数時間検査可能であることを示してきたが、ボタン＆シザーズが定数時間検査不可能だとの予想を立てて証明を試みている。そして盤面を一次元に限った問題については定数時間検査不可能であることに対する我々の構築した証明が不完全であることを見つけた。具体的には、既に定数時間検査不可能であることが証明されている文字列問題を帰着することで行っているが、帰着の際に想定外のボタン消去手順が存在することを見落としていた。現在その証明を修正中である。 (II) 離散幾何学上の問題に対していくつか成果を上げた。まずDNA計算などに応用を持つ、ある種の折れ線の非交差平面埋め込み問題がNP完全であることを証明した。これはErik Demaine (MIT)らとの共同研究であり、国際会議CCCG2022のプロシーディングスに掲載された。他に多面体の全ての面を通る測地路であるFGG路(Face-Guard Geodesic Path)という概念を提示し、それを持つ多面体の特徴づけを行った。具体的には任意の四面体にはFGG路が存在するが、正四面体以外の正多面体にはFGG路は存在しない事、三角柱にFGG路の存在する必要十分条件などを明らかにした。また、数字の配置が均衡しているn面体ダイスの問題などに関する研究も行い、それらを国際会議JCDCG^3 2022で発表し、論文を投稿した。現在査読中である。