Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2202.08214 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917426674794496 |
|---|---|
| author | Part, Fedor |
| author_facet | Part, Fedor |
| contents | 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}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_08214 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Lower Bounds for Subset Sum in Resolution with Modular Counting Part, Fedor Computational Complexity 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}$. |
| title | Lower Bounds for Subset Sum in Resolution with Modular Counting |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2202.08214 |