Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2403.03933 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916306598494208 |
|---|---|
| author | Mouli, Sasank |
| author_facet | Mouli, Sasank |
| contents | For every $n >0$, we show the existence of a CNF tautology over $O(n^2)$ variables of width $O(\log n)$ such that it has a Polynomial Calculus Resolution refutation over $\{0,1\}$ variables of size $O(n^3polylog(n))$ but any Polynomial Calculus refutation over $\{+1,-1\}$ variables requires size $2^{Ω(n)}$. This shows that Polynomial Calculus sizes over the $\{0,1\}$ and $\{+1,-1\}$ bases are incomparable (since Tseitin tautologies show a separation in the other direction) and answers an open problem posed by Sokolov [Sok20] and Razborov. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_03933 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable Mouli, Sasank Computational Complexity Logic For every $n >0$, we show the existence of a CNF tautology over $O(n^2)$ variables of width $O(\log n)$ such that it has a Polynomial Calculus Resolution refutation over $\{0,1\}$ variables of size $O(n^3polylog(n))$ but any Polynomial Calculus refutation over $\{+1,-1\}$ variables requires size $2^{Ω(n)}$. This shows that Polynomial Calculus sizes over the $\{0,1\}$ and $\{+1,-1\}$ bases are incomparable (since Tseitin tautologies show a separation in the other direction) and answers an open problem posed by Sokolov [Sok20] and Razborov. |
| title | Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable |
| topic | Computational Complexity Logic |
| url | https://arxiv.org/abs/2403.03933 |