用于稀疏系数提取的同态哈希

### 用于稀疏系数提取的同态哈希 #### 1. 引言 系数提取可视为一种通用的算法设计方法，尤其在各类NP难问题的精确算法领域。其方法步骤如下： 1. 定义一个变量（即所谓的系数），其值几乎能直接给出待解决问题的解。 2. 证明该变量可以通过一个相对较小的公式或电路，在一个（巧妙选择的）大型代数对象（如环或域）上表示出来。 3. 展示如何在代数对象中相对高效地执行操作。 在该方法的典型应用中，前两个步骤通常源自现有的动态规划（DP）算法，而第三步则采用精心挑选的代数同构，如离散傅里叶变换，来提取所需的解或系数。基于系数提取的算法相较于DP算法有两个关键优势：空间效率高且易于并行化。 然而，如果问题实例是稀疏的，DP算法则具有优势。这里的稀疏指的是在DP过程中需要考虑的候选/部分解的数量较少，即DP表中的大多数条目根本未被使用。在这种情况下，可以通过记忆化轻松调整DP算法，使运行时间和空间使用与考虑的部分解的数量成正比。但记忆化难以并行化或降低空间使用。依赖稀疏多项式插值的系数提取算法虽然在一定程度上有所改进，但空间使用仍不理想。 本文旨在结合两者的优势，研究系统地使用同态哈希函数将基于电路的系数提取算法“哈希化”，使系数提取的域（进而运行时间）与基于记忆化的DP算法相匹配或更优，同时提供空间效率和高效并行化。这种方法被称为同态哈希。 #### 2. 相关研究与成果 我们在三个领域研究稀疏DP/系数提取： - 一元多项式环Z[x]。 - 群代数F[Zn₂]，其中F是奇特征域。 - 子集格的莫比乌斯代数。 稀疏DP或系数提取是一个备受关注且研究充分的主题。之前已有针对前两个领域的稀疏多项式插值算法，但使用的是指数空间，我们的算法将其改进为多项式空间。我们的主要技术贡献在于第三个领域，即哈希到偏序集的“所罗门代数”。 我们的方法适用于一般算术电路，大多数算法也适用于计数变体。为了具体说明，我们将处理特定的决策问题。虽然主要针对这些问题的稀疏变体进行改进，但这些结果对处理一般情况也可能有用。 #### 3. 子集和问题 子集和问题是指：给定一个向量a = (a₁, ..., aₙ)和整数t，确定是否存在一个子集X ⊆ [n]，使得∑ₑ∈ₓ aₑ = t。已知该问题可在O⋆(2ⁿ/²)时间和O⋆(2ⁿ/⁴)空间内解决，更快地解决该问题，甚至在O⋆(1.99ⁿ)时间和多项式空间内解决仍是有趣的开放问题。 标准的稀疏DP算法给出了O⋆(S)时间和O⋆(S)空间的算法，其中S = |{∑ₑ∈ₓ aₑ : X ⊆ [n]}|是不同和的数量。我们将其改进为多项式空间： - 定理1：任何子集和问题的实例(a, t)可以在以下条件下解决： - (a) 期望时间O⋆(S)和多项式空间。 - (b) 时间O⋆(S²)和多项式空间。 我们的算法通过对实例进行模随机选择的素数运算并应用相关算法来实现。这些结果在结合其他技术时，可能有助于解决上述开放问题。 #### 4. 线性可满足性问题 线性可满足性问题定义为：给定一个矩阵A ∈ Zn×m₂，向量b ∈ Zm₂和ω ∈ Nⁿ，以及整数t = nO(1)，确定是否存在一个向量x ∈ Zn₂，使得xA = b且ωxᵀ ≤ t。该问题的变体已有研究。 使用特定方法，线性可满足性问题可以在O(2ⁿ/²m)时间和O(2ⁿ/²m)空间内解决。标准的“稀疏动态规划”可以在O⋆(2ʳᵏ(A))时间和O⋆(2ʳᵏ(A))空间内解决，其中rk(A)