DocumentCode
2346382
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
fYear
1994
fDate
17-20 Nov 1994
Firstpage
151
Lastpage
155
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Physics and Computation, 1994. PhysComp '94, Proceedings., Workshop on
Conference_Location
Dallas, TX
Print_ISBN
0-8186-6715-X
Type
conf
DOI
10.1109/PHYCMP.1994.363687
Filename
363687
Link To Document