Answers are grounded in this paper and cite their sources.
We characterize the single-pass streaming space complexity of Boolean CSP satisfiability in the strict-turnstile model for every fixed constraint language $Γ$ of k-ary Boolean relations that is not trivially satisfiable. Constraints can be inserted or deleted with nonnegative multiplicities; satisfiability is decided for those remaining at the end. While Sharma and Velusamy [ESA 2026] characterized insertion-only complexity via non-redundancy (up to logarithmic factors), we show that strict-turnstile complexity is governed by the integer capturing degree. For R⊆\0,1\ᵏ, let dR be the minimum degree of an integer-coefficient polynomial vanishing exactly on R over the Boolean hypercube, and set d_Γ=maxR∈ΓdR. On polynomial-length streams, we obtain an Oₖ(nd_Γpolylog n)-space randomized algorithm and an Ωₖ(nd_Γ/log n) lower bound for all algorithms. Moreover, our algorithm outputs a sparse instance preserving every satisfying assignment. This yields, to our knowledge, the first insertion-only versus turnstile separation for streaming CSPs. It also differs from the Fourier-degree characterization of exact optimization by Kol, Paramonov, Saxena, and Yu [ITCS 2023]. For k≥3, k-XOR with literals has three distinct space complexities: Θ(n) for insertion-only satisfiability, Θ(nk/2) for strict-turnstile satisfiability, and Θ(nᵏ) for exact optimization in either model.
No takes yet. Share an insight, caveat, or question.
Bandekar et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: