2023-10-02T14:44:17Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001472132023-04-27T10:00:04Z01164:02592:08452:08453
Synchronous Boolean Finite Dynamical Systems and Minimum Circuit Size ProblemSynchronous Boolean Finite Dynamical Systems and Minimum Circuit Size Problemenghttp://id.nii.ac.jp/1001/00147179/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=147213&item_no=1&attribute_id=1&file_no=1Copyright (c) 2016 by the Information Processing Society of JapanDepartment of Computer Science, University of MiamiFaculty of Engineering, Yamagata UniversityMitsunori, OgiharaKei, UchizawaWe study synchronous Boolean finite dynamical systems (synchronous BFDSs) consisting of some finite number of objects, where a local transition function on each object is chosen from a simple basis B. Specifically, we focus on the case where the basis B is one of {AND}, {OR} and {XOR,NXOR}. We show that, in these settings, the following two problems are randomized polynomial-time reducible to Minimum Circuit Size Problem: (i) Given an n-object synchronous BFDS F and two state configurations a and b, do there exist time steps s and t, such that the state configuration of F on a at step s is equal to the state configuration of F on b at step t? (ii) Given an n-object synchronous BFDS F, an initial state configuration a, and an integer t, is the state configuration sequence generated by F starting from a contains a cycle having length greater than or equal to t?We study synchronous Boolean finite dynamical systems (synchronous BFDSs) consisting of some finite number of objects, where a local transition function on each object is chosen from a simple basis B. Specifically, we focus on the case where the basis B is one of {AND}, {OR} and {XOR,NXOR}. We show that, in these settings, the following two problems are randomized polynomial-time reducible to Minimum Circuit Size Problem: (i) Given an n-object synchronous BFDS F and two state configurations a and b, do there exist time steps s and t, such that the state configuration of F on a at step s is equal to the state configuration of F on b at step t? (ii) Given an n-object synchronous BFDS F, an initial state configuration a, and an integer t, is the state configuration sequence generated by F starting from a contains a cycle having length greater than or equal to t?AN1009593X研究報告アルゴリズム（AL）2016-AL-1565152016-01-142188-85662016-01-07