@techreport{oai:ipsj.ixsq.nii.ac.jp:00217775, author = {井上, 太智 and 北村, 直暉 and 泉, 泰介 and 増澤, 利光 and Taichi, Inoue and Naoki, Kitamura and Taisuke, Izumi and Toshimitsu, Masuzawa}, issue = {12}, month = {May}, note = {本稿では,????(1) ビットの頂点記憶領域を持つサイズ ???? の匿名な無向リングにおいて,1 体のエージェントが動作するシステムの計算能力について検討する.具体的には,当該のシステム上で動作するエージェントが無記憶である場合と 1 ビットの永続記憶を持つ場合について,後者のエージェントで動作するアルゴリズムを,前者のエージェントが 1 ステップ動作あたり ????(????) 時間のオーバーヘッドでシミュレーションするアルゴリズムを提案することにより,多項式時間求解性の意味で両者の計算能力が等価であることを示す., We consider the system where a single mobile agent is deployed in an anonymous, oriented, and undirected ring of ???? vertices with ????(1)-bit storage. We focus on the computational power of this system, in both cases of oblivious agents and non-oblivious agents with one-bit memory. The main contribution of this paper is to show that these two cases are equivalent with respect to the polynomial-time solvability of any given task, by presenting an algorithm of simulating any algorithm for one-bit memory agents by oblivious agents with ????(????)-time overhead per one step simulation.}, title = {無向リングにおける無記憶モバイルエージェントの計算能力}, year = {2022} }