Development of the sublinear-time paradigm

亚线性时间范式的发展

• 批准号: 20K11671
• 负责人: 伊藤 大雄
• 金额: $ 2.75万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K11671/
• 关键词: 定数時間アルゴリズム; 検査不可能性; 折れ線の非交差埋め込み問題; 劣線形時間アルゴリズム; 漸進型アルゴリズム; オンラインアルゴリズム; 競合比; 離散アルゴリズム; グラフ; 幾何学; ゲーム・パズル; 折り紙; 複雑ネットワーク

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

这项研究正在进行理论研究，以广泛地开发主要研究者提出的“均方根时间范式”。 2022财政年度的主要结果如下：（i）我们正在进行研究，以将恒定和均匀的时间算法扩展到游戏难题中。到目前为止，一些广义的游戏难题表明可以检查它们一个固定的小时，但是Button和剪刀试图证明它们无法在固定的小时内进行检查。然后，我们发现我们对限制董事会限制一维的问题的不完整检查的构建证明是不完整的。具体而言，此方法是通过红外字符串问题执行的，这些问题已经被证明是不变的时间，但它忽略了返回时意外的按钮擦除过程。目前正在修改证明。 （ii）在离散的几何问题上已经取得了一些成就。首先，我们已经证明，在DNA计算中具有应用的某些非交叉平面嵌入问题是NP完整的。这是与Erik Demaine（MIT）等人的联合研究项目，并在CCCG2022国际会议上发表在会议录中。我们还介绍了面孔的大地测量路径（面坚固的大地测量路径）的概念，这是一种经过多面体的所有面，并用它表征了多面体。具体而言，尽管在任何四面体中都存在FGG路径，但除常规四面体以外的常规多面体中没有FGG路径，并且阐明了三角形棱镜上存在FGG路径的必要条件。他还研究了N-Hedral Dice的问题，该数字安排是平衡的，并在国际会议JCDCG^3 2022中介绍了它们，并提交了他的论文。目前正在同行评审中。

项目成果

Sublinear Computation Paradigm: Constant-Time Algorithms and Sublinear Progressive Algorithms

• DOI: 10.1587/transfun.2021eai0003
• 发表时间: 2022
• 期刊: IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
• 作者: Kyohei Chiba;Hiro Ito

凸等面多面体ダイスの数均衡制約

凸等边多面体骰子的数平衡约束

• 发表时间: 2023
• 作者: 爲近理渚;伊藤大雄
• 通讯作者: 伊藤大雄

Numerically balanced dice on isohedral polyhedron

等面多面体上的数值平衡骰子

• 发表时间: 2022
• 作者: Hiro Ito;Kanaya Shunsuke;and Risa Tamechika
• 通讯作者: and Risa Tamechika

Geodesic paths passing through all faces on a polyherdon

穿过多角体上所有面的测地线路径

• 发表时间: 2022
• 作者: Erik Demaine;Martin Demaine;David Eppstein;Hiro Ito;Yuta Katayama;Wataru Maruyama;and Yushi Uno
• 通讯作者: and Yushi Uno

Univ. Nevada, Las Vegas/MIT(米国)

内华达大学拉斯维加斯/麻省理工学院（美国）