论文标题
分辨率的子集总和的下限和模块化计数
Lower Bounds for Subset Sum in Resolution with Modular Counting
论文作者
论文摘要
在本文中，我们证明了不满意的向量子集总和实例$ \ oferrightArrow {a} _1 x_1 + \ dots + \ oftrightArrow {a} _n x_n x_n = \ oftrightArrow {b cooterrightArrow {b} $ lin $ _________________ $ char（\ mathbb {f} _ {q}）\ geq 5 $。作为此类实例硬度标准的基础，我们选择了矩阵$ a $的属性，并带有列$（\ oferrightArrow {a} _1，\ ldots，\ costrightArrow {a} _n）$（be（a} _n）$（be（the）的the transpose be（the the transpose）生成型矩阵的良好误差代码$ cod $ c _} | \，x \ in \ mathbb {f} _ {q}^k \} \ subset \ subset \ mathbb {f} _ {q}^n $并证明以下下限： 1）对于res（lin $ _ {\ mathbb {f} _q} $）的类似dag的片段。我们介绍了子集和实例的$（s，r）$ - 鲁棒性的概念，这尤其暗示$ a $用最小距离$ s \ geq r $定义了错误校正的代码。对于$（s，r）$ - 稳健的实例，我们证明$ 2^{ω（r）} $下限制了Res类似于DAG的片段（lin $ _ {\ Mathbb {f} _Q} $）中的反驳尺寸。我们表明，随机实例为$（n/3，ω\ left（（（n/（q + 1）\ ln q））^{1/3} \ right））$ - 可靠的范围可以使用代数几何形状代码来构建实现这些边界的特定示例。 2）对于类似树的res（lin $ _ {\ mathbb {f} _q} $）反驳我们显示了大小下限$ 2^{ω（{（（q+1）\ ln q）
In this paper we prove lower bounds for sizes of refutations of unsatisfiable vector Subset Sum instances $\overrightarrow{a}_1 x_1 + \dots + \overrightarrow{a}_n x_n = \overrightarrow{b}$ in the proof system Res(lin$_{\mathbb{F}_q}$) where $char(\mathbb{F}_{q})\geq 5$. As a basis for the hardness criterion for such instances we choose the property of the matrix $A$ with columns $(\overrightarrow{a}_1, \ldots, \overrightarrow{a}_n)$ to be (the transpose of) the generating matrix for a good error-correcting code $C_{A} := \{x\cdot A\, |\, x \in \mathbb{F}_{q}^k\}\subset \mathbb{F}_{q}^n$ and prove the following lower bounds: 1) For a dag-like fragment of Res(lin$_{\mathbb{F}_q}$). We introduce the notion of $(s,r)$-robustness for Subset Sum instances, which in particular implies that $A$ defines an error-correcting code with the minimal distance $s\geq r$. For $(s,r)$-robust instances we prove $2^{Ω(r)}$ lower bound for sizes of refutations in a dag-like fragment of Res(lin$_{\mathbb{F}_q}$). We show that random instances are $(n / 3, Ω\left((n/(q + 1)\ln q))^{1/3}\right))$-robust and that specific examples achieving these bounds can be constructed using algebraic geometry codes. 2) For tree-like Res(lin$_{\mathbb{F}_q}$) refutations we show the size lower bound $2^{Ω({((q+1)\ln q)^{-1/3}}d^{1/5})}$ for any Subset Sum instance where $d$ is the minimal distance of $C_{A}$.
