Lower Bounds on Inverse Cellular Automata via Proof Complexity

Maryia Kapytka · 2026

Read Lower Bounds on Inverse Cellular Automata via Proof Complexity by Maryia Kapytka (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-01041.txt.

Introduction

Kapytka studies the hardness of inverse cellular automata on bounded-size configurations. Deciding injectivity there is co-NP-complete by Durand's theorem, and she gives a simpler proof by direct reduction from UNSAT. She shows the weak bounded arithmetic theory V0 can formalize one direction of the reduction. Since Durand's result lets inverse cellular automata on bounded configurations be viewed as propositional proofs, she proves lower bounds on their size. She uses known bounded-depth Frege bounds plus the Paris-Wilkie translation of arithmetic proofs into propositional proofs.

Catalog record

CREATORMaryia Kapytka
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE104090
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.01041

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Lower Bounds on Inverse Cellular Automata via Proof Complexity Maryia Kapytka Abstract We study the complexity of inverse cellular automata on configurations of bounded size. Deciding injectivity in this setting is co-NP-complete by a theorem of Durand [ 6 ] . We give a simpler proof of this theorem by a direct reduction from UNSAT \mathrm{UNSAT} to this problem, avoiding more complicated intermediate constructions. We also show that one direction of the reduction can be formalized in the weak theory of bounded arithmetic V 0 V^{0} . Durand’s coNP-completeness result allows one to view inverse cellular automata acting on bounded size configurations as propositional proofs, cf. Cavagnetto [ 2 , 3 ] , and we prove lower bounds on their size. The proof uses known lower bounds for bounded-depth Frege systems together with the Paris–Wilkie translation of arithmetic proofs into propositional proofs, which allows us to transfer proof complexity lower bounds to our setting. 1 Introduction Cellular automata are simple models of systems that change in steps, widely used in computer science and physics. They capture basic features of nature like local interactions, uniform rules, and parallel updates. A key concept is the Garden of Eden, a configuration that cannot arise from any previous state. The Garden of Eden theorem characterizes when such configurations exist. A cellular automaton is surjective if and only if every configuration has a predecessor; that is, if and only if it has no Garden of Eden configuration. This is further linked to local injectivity: two finite patterns are called twins if they can be swapped anywhere without affecting future configurations; the automaton is locally injective if it has no twins. The theorem states that surjectivity and local injectivity are equivalent. In two dimensions, Kari [ 7 ] showed that checking injectivity or surjectivity is undecidable, meaning no algorithm can solve it in general. However, the situation changes when we restrict attention to bounded configurations. In this setting, the problem becomes decidable but remains computationally difficult. In particular, Durand [ 6 ] proved that deciding injectivity of two-dimensional cellular automata on bounded configurations is coNP-complete, implying that, unless \mathrm{P}=\mathrm{NP} , this problem is computationally hard. His proof uses a complex multi-step reduction from the nondeterministic halting problem via tiling systems. In this paper, we give a more direct reduction. More precisely, we introduce a polynomial reduction of the coNP-complete set \mathrm{UNSAT} (the set of unsatisfiable CNF formulas) to the set of injective two-dimensional cellular automata with von Neumann neighbourhood on configurations of bounded size. Moreover, we show that one direction of this reduction (namely, that if the formula is satisfiable, then the cellular automaton is not injective) can be formalized in the theory V^{0} , a weak theory of bounded arithmetic. Since V^{0} is extremely weak, formalizing such a complexity-theoretic result within it is not straightforward. While several unprovability results are known for V^{0} , few non-trivial theorems of this kind have been shown to be provable inside it. Durand [ 6 , Sec. 4] posed the question of whether the inverse automaton to a cellular automaton operating on bounded configurations, whose transition function is computed by a simple algorithm, is also computed by a simple algorithm. Cavagnetto [ 2 , Sec. 3.3] showed, using the computational complexity hypothesis that a one-way function exists, that this is not the case if by an algorithm one means a Boolean circuit. In addition, he showed that Durand’s coNP-completeness results still hold in such a setup. The question of the size of inverse cellular automata for the original representation of the transition function by its table was left open in both [ 6 , 2 ] . We shall use proof complexity to solve this problem. The motivation for our approach comes from the PhD thesis of Stefano Cavagnetto [ 2 ] , which was later published in [ 3 ] . In that work, inverse cellular automata were viewed as propositional proofs in the sense of Cook–Reckhow [ 5 ] . We follow this idea. We show that, when we restrict ourselves to configurations of bounded size, cellular automata in our construction have the property that inverse automata to them cannot be in general of subexponential size. Indeed, their size is exponential, and, in particular, their neighborhood must grow polynomially. To prove this, we consider the unsatisfiable CNF formula \varphi=\lnot\mathrm{ontoPHP}_{k} , which expresses that there is a bijection between k+1 and k . This formula has size polynomial in k but requires exponential-size bounded-depth Frege refutations by known strengthenings of a theorem of Ajtai [ 1 ] . Then we use the Paris–Wilkie translation [ 9 ] to simulate our inverse cellular automaton proof system by a bounded-depth Frege system F_{d} , thereby transferring this lower bound to our setting. For background on cellular automata, see for example [ 7 ] , and for background on bounded arithmetic and proof complexity, see [ 8 ] . 2 Preliminaries Throughout the paper we use the notation [n]:=\{0,1,\dots,n-1\} . 2.1 Cellular automata We briefly recall the basic notions of cellular automata that will be needed later. The definitions are standard and follow [ 6 ] , but we include them here to fix notation and terminology. We also record a simple bound on the size needed to encode a two-dimensional cellular automaton with a fixed neighbourhood. Definition 2.1 (Cellular automaton) . A cellular automaton is formally defined as a quadruplet (d,S,N,f) : • The integer d\geq 1 is the dimension of the space on which the cellular automaton operates. • S\not=\emptyset is a finite set called the set of states . • The neighbourhood N is a v -tuple of distinct vectors of \mathbb{Z}^{d} . For N=(x_{1},...,x_{v}) , vectors x_{i} are the relative positions of the neighbour cells with respect to a given center cell. The states of these neighbours are used to compute the new state of the center cell. • The local function of the cellular automaton f:S^{v}\to S gives the local transition rule. A configuration is a map C:\mathbb{Z}^{d}\to S . For a configuration C and a position y\in\mathbb{Z}^{d} , the value C(y) is called the state of the cell at position y . We refer to the position y itself as a cell . If C:\mathbb{Z}^{d}\to S is a configuration, we identify C with its graph \{\,((i,j),C(i,j))\mid(i,j)\in\mathbb{Z}^{d}\,\}. All automata considered in this paper are two-dimensional, i.e. d=2 . Sometimes, a state q for which f(q,q,\dots,q)=q is distinguished in S and is called a quiescent state. A finite configuration is a configuration which has only a finite number of cells in a non-quiescent state. If there exist two integers i and j such that all non-quiescent cells of the configuration are located inside a rectangle with coordinates in [i]\times[j] , then we say that the finite configuration is inside [i]\times[j] . We shall be interested in how automata operate on configurations inside a fixed rectangle. Lemma 2.2 . ( [ 6 ] ) For fixed N (of size v ) the size of a binary string sufficient to code a cellular automaton of dimension d=2 is bounded above by s^{v}\log s , where s is the size of S . Proof. We have d=2 and a fixed

Read the complete text