Characterizing Streaming Decidability of CSPs via Non-Redundancy
2026-04-23 • Data Structures and Algorithms
Data Structures and AlgorithmsComputational Complexity
AI summaryⓘ
The authors study how much memory is needed to decide if a set of constraints can all be satisfied when the constraints come in one by one. They work with a general type of problems called CSPs, where each constraint involves some variables and conditions based on modular arithmetic. Previous work found memory bounds for specific cases, but the exact memory needed for general CSPs was unknown. The authors show that the memory needed depends on a property called non-redundancy, which measures how many constraints you can have where each constraint matters independently. Essentially, they precisely link the memory complexity to this non-redundancy measure.
Constraint Satisfaction ProblemsStreaming ModelSingle-Pass StreamingMemory ComplexityNon-Redundancyk-ary RelationsModular ArithmeticLower BoundCSP(Γ)Computational Complexity
Authors
Amatya Sharma, Santhoshini Velusamy
Abstract
We study the single-pass streaming complexity of deciding satisfiability of Constraint Satisfaction Problems (CSPs). A CSP is specified by a constraint language $Γ$, that is, a finite set of $k$-ary relations over the domain $[q] = \{0, \dots, q-1\}$. An instance of $\mathsf{CSP}(Γ)$ consists of $m$ constraints over $n$ variables $x_1, \ldots, x_n$ taking values in $[q]$. Each constraint $C_i$ is of the form $\{R_i,(x_{i_1} + λ_{i_1}, \ldots, x_{i_k} + λ_{i_k})\}$, where $R_i \in Γ$ and $λ_{i_1}, \ldots, λ_{i_k} \in [q]$ are constants; it is satisfied if and only if $(x_{i_1} + λ_{i_1}, \ldots, x_{i_k} + λ_{i_k}) \in R_i$, where addition is modulo $q$. In the streaming model, constraints arrive one by one, and the goal is to determine, using minimum memory, whether there exists an assignment satisfying all constraints. For $k$-SAT, Vu (TCS 2024) proves an optimal $Ω(n^k)$ space lower bound, while for general CSPs, Chou, Golovnev, Sudan, and Velusamy (JACM 2024) establish an $Ω(n)$ lower bound; a complete characterization has remained open. We close this gap by showing that the single-pass streaming space complexity of $\mathsf{CSP}(Γ)$ is precisely governed by its non-redundancy, a structural parameter introduced by Bessiere, Carbonnel, and Katsirelos (AAAI 2020). The non-redundancy $\mathsf{NRD}_n(Γ)$ is the maximum number of constraints over $n$ variables such that every constraint $C$ is non-redundant, i.e., there exists an assignment satisfying all constraints except $C$. We prove that the single-pass streaming complexity of $\mathsf{CSP}(Γ)$ is characterized, up to a logarithmic factor, by $\mathsf{NRD}_n(Γ)$.