Title :
On the average-case complexity of the reversibility problem for finite cellular automata
Author :
Clementi, A. ; Pierini, P. ; Impagliazzo, R.
Author_Institution :
Dept. of Comput. Sci., La Sapienza Univ., Rome, Italy
Abstract :
Of particular relevance in the theory and applications of cellular automata is the concept of invertibility. We study the computational complexity of deciding whether or not a given finite cellular automata is invertible. This problem is known to be CoNP-complete, we prove that the expected-time complexity of its randomized version is “hard”: the problem is CoRNP-complete. Finally, we discuss some consequences of this result in the theory and applications of cellular automata
Keywords :
cellular automata; computational complexity; finite automata; CoNP-complete; average-case complexity; cellular automata; finite cellular automata; invertibility; reversibility; Application software; Automata; Cellular manufacturing; Computational complexity; Computer science; Mathematical model; Mathematics; Physics computing; Polynomials; Topology;
Conference_Titel :
Physics and Computation, 1994. PhysComp '94, Proceedings., Workshop on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-6715-X
DOI :
10.1109/PHYCMP.1994.363687
