http://swrc.ontoware.org/ontology#TechnicalReport
Synchronous Boolean Finite Dynamical Systems and Minimum Circuit Size Problem
en
Department of Computer Science, University of Miami
Faculty of Engineering, Yamagata University
Mitsunori Ogihara
Kei Uchizawa
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?
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-156
5
1-5
2016-01-14
2188-8566