Lower Bounds for Subset Sum in Resolution with Modular Counting

Abstract

In this paper we prove lower bounds for sizes of refutations of unsatisfiable vector Subset Sum instances ${\overrightarrow{a}}_1{x}_1+\cdots +{\overrightarrow{a}}_n{x}_n=\overrightarrow{b}$ in the proof system Res(lin${}_{{\mathbb{F}}_q}$) where $char({\mathbb{F}}_q)\ge 5$. As a basis for the hardness criterion for such instances we choose the property of the matrix $A$ with columns $({\overrightarrow{a}}_1,\dots ,{\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\ge r$. For $(s,r)$-robust instances we prove $2^{\Omega (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,\Omega \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^{\Omega (((q+1)\ln q{)}^{-1/3}{d}^{1/5})}$ for any Subset Sum instance where $d$ is the minimal distance of $C_A$.