Characterizing Streaming Decidability of CSPs via Non-Redundancy

判斷一組約束方程式是否可滿足，streaming 演算法到底需要多少記憶體？2026 年 4 月，Sharma 與 Velusamy 以單一參數「非冗餘度 NRD」給出精確答案，誤差僅對數因子，同時首度揭示：streaming 下可滿足性判定可以遠比最大化版本（Max-CSP）容易——例如 k-LIN 線性方程組只需 O(n log n) 空間，Max-k-LIN 卻要 Θ(n^k)，差距指數級。

懸而未決的 streaming CSP 空間刻畫問題

約束滿足問題（CSP，Constraint Satisfaction Problem）是涵蓋 k-SAT、圖著色、線性方程組等各類判定問題的通用理論框架。在 streaming 模型中，約束條件逐條流入，演算法必須以有限記憶體在串流結束後判斷是否存在一個賦值同時滿足所有約束。這個問題的平凡上界是儲存全部 O(n^k) 條約束。2024 年，Vu 對 k-SAT 給出了匹配的 Ω(n^k) 下界；同年，Chou 等人給出一般 CSP 的 Ω(n) 下界。兩者之間的巨大空缺——哪些 CSP 需要二次方乃至 k 次方空間？哪些只需線性？——正是本文填補的核心問題。

非冗餘度 NRD：源自 AAAI 2020 的結構參數

本文的關鍵參數是非冗餘度 NRD_n(Γ)，最初由 Bessiere、Carbonnel 與 Katsirelos 在 AAAI 2020 針對 CSP 學習問題引入，此後被發現同時支配了精確稀疏化（exact sparsification）、核化（kernelization）以及近似稀疏化的複雜度。本文進一步確立其對 streaming 複雜度的支配地位，使 NRD 成為 CSP 理論迄今最具統一性的結構指標。

NRD_n(Γ) 定義為 n 個變數上最大非冗餘實例的規模。「非冗餘」指：移除任何一條約束都會嚴格增加滿足解的數量。等價地，每條約束 C 都存在「見證賦值」a_C，它滿足其他所有約束、但唯獨不滿足 C 本身。幾個具體數值：k-SAT 的 NRD_n = Θ(n^k)（完全圖上的 OR 子句實例就是非冗餘的）；k-LIN（F₂ 上的線性方程組）的 NRD_n = Θ(n)；圖 q-著色（q ≥ 3，即關係 x ≠ y）的 NRD_n = Θ(n²)。對任何非平凡約束語言，NRD_n(Γ) ≥ Ω(n)。

主定理：上界 O(NRD · log n)，下界 Ω(NRD)

Theorem 1.1 是本文的核心結論：對任意約束語言 Γ，存在確定性 streaming 演算法用 O(NRD_n(Γ) · log n) 空間判定可滿足性；任何隨機化 streaming 演算法（成功率 ≥ 2/3）都需要 Ω(NRD_n(Γ)) 空間。

上界演算法思路極為簡潔：始終維護一個與已見約束等價且非冗餘的子實例。每當新約束 C 到來，先暫時加入當前子實例，再反覆刪除其中的冗餘約束，直到整體恢復非冗餘狀態。由於只刪除冗餘約束，滿足解集全程不變；儲存的約束數不超過 NRD_n(Γ)，每條約束只需 O(log n) 位元，總空間即 O(NRD_n(Γ) · log n)。值得注意的是，這個演算法維護了完整的等價子實例，因此同時給出了 streaming 精確稀疏化與 streaming 枚舉的相同空間上界，且相同的 Ω(NRD_n) 下界對這兩個更困難的問題同樣成立。

等價類定理：ℰ 關係的對稱性由加法平移結構保證

下界的核心工具是對賦值集合 [q]^n 定義的二元關係 ℰ：若每個被賦值 a 滿足的實例也被賦值 b 滿足，則 (a, b) ∈ ℰ。自反性與傳遞性顯然，但對稱性——若 (a,b) ∈ ℰ 是否必有 (b,a) ∈ ℰ——並不直觀。Theorem 4.2（等價類定理） 證明：對一般 CSP，ℰ 確實構成等價關係。

證明利用 CSP 模型中天然存在的加法平移結構。令 Δ = a − b（模 q），平移算子 τ_Δ 使「z 滿足 τ_Δ(J)」等價於「z + Δ 滿足 J」。因此，a 所滿足的實例集合 S_a 與 b 所滿足的集合 S_b 之間存在 τ_Δ 建立的雙射，故 |S_a| = |S_b|。又因 (a, b) ∈ ℰ 蘊含 S_a ⊆ S_b，兩者有限且等大，必然 S_a = S_b，從而 (b, a) ∈ ℰ，對稱性成立。等價類定理還有一個建構性推論：對每個賦值 a，都存在實例 P_a 使其滿足解集恰好等於 a 的等價類 [a]_ℰ，做法是將所有「a 滿足但不在 [a]_ℰ 中的賦值 u 不滿足」的實例取聯集，有限域保證其存在性。

從 INDEX 通訊問題推導 Ω(NRD) 空間下界

下界採用 streaming 複雜度的標準手法：把 streaming 演算法轉化為單向通訊協議，再以通訊困難性推導空間下界。出發點是 INDEX_m 問題：Alice 持有 m 位字串 x，Bob 持有索引 i，Alice 只允許發送一條訊息，Bob 必須輸出 x_i。任何成功率 ≥ 2/3 的隨機單向協議都需要 Ω(m) 位元（Ablayev 1996 的經典結果）。

規約構造如下：以 CSP(Γ) 在 n 個變數上的最大非冗餘實例 I_n（規模 NRD_n(Γ)）為框架，Alice 持有 I_n 的某個子實例 I，Bob 持有 I_n 中某條約束 C，共同判斷 C 是否屬於 I。由 I_n 的非冗餘性，C 有見證賦值 a_C 滿足 I_n 中其他所有約束、但不滿足 C。利用等價類定理，Bob 構造後綴實例 I_C，使其滿足解集恰為 [a_C]_ℰ。規約的邏輯閉合：若 C ∈ I，則 a_C 不滿足 I（因其不滿足 C），I ∪ I_C 不可滿足；若 C ∉ I，則 a_C 滿足 I，I ∪ I_C 可滿足。因此 streaming 演算法能解決 INDEX_m（m = NRD_n(Γ)），空間不低於 Ω(NRD_n(Γ))。

正布林 CSP 限制與 Max-CSP 的指數級難度差距

論文同時處理了兩個延伸方向。對正布林 CSP（不對變數取反，例如圖二著色），若語言是「常數可滿足」的（全 0 或全 1 賦值就能滿足一切），下界自然失效；限縮到非常數可滿足語言後，Theorem 3.1 確認同樣的 Ω(NRD_n) 下界有效。論文同時給出兩個反例，說明對 q > 2 的正 CSP，ℰ 的對稱性可能失效，streaming 可滿足性確實嚴格容易於 NRD_n(Γ)，刻畫無法推廣至此情形。

在與 Max-CSP 的對比上，Kol 等人（2021）已完整刻畫 Max-CSP streaming 複雜度：Max-k-LIN 需要 Θ(n^k) 空間。本文顯示可滿足性版本的 k-LIN 只需 O(n log n)——兩者相差指數級，是 streaming 場景下首個清晰展示「可滿足性比最大化指數級容易」的例子。對 Min-CSP，任何非平凡近似必然繼承可滿足性的空間下界，圖 q-著色（NRD_n = Θ(n²)）即是在任何非平凡近似下都需二次方空間的代表性例子。

非冗餘度 NRD 同時刻畫 streaming 可滿足性、精確稀疏化與核化複雜度，是 CSP 理論中精簡而統一的結構核心。