2025/04/07 by Tom Favereau, Ville Salo, Favereau, Tom +1
Computer Science · #37B15 (Primary) #68Q80 (Secondary) #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2504.05012
openalex publication_date 2025/04/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the computational complexity of determining whether a cellular automaton is sensitive to initial conditions. We show that this problem is Π02-complete in dimension 1 and Σ03-complete in dimension 2 and higher. This solves a question posed by Sablik and Theyssier.