Résumé
In this paper, we prove the co-RNP-completeness (RNP = Random NP) of the following decision problem: “Given a 2-dimensional cellular automaton
A
, is
A
reversible when restricted to finite configurations extending a given row?” In order to prove this result, we introduce a polynomial reduction from problems concerning finite tilings into problems concerning cellular automata. Then we add to tile sets and cellular automata probability functions and we prove that these problems are not only co-NP-complete, but co-RNP-complete too.