ECCC-Report TR13-077https://eccc.weizmann.ac.il/report/2013/077Comments and Revisions published for TR13-077en-usFri, 24 May 2013 17:44:34 +0300
Paper TR13-077
| Circuit Lower Bounds in Bounded Arithmetics |
Ján Pich
https://eccc.weizmann.ac.il/report/2013/077We prove that $T_{NC^1}$, the true universal first-order theory in the language containing names for all uniform $NC^1$ algorithms, cannot prove that for sufficiently large $n$, SAT is not computable by circuits of size $n^{2kc}$ where $k\geq 1, c\geq 4$ unless each function $f\in SIZE(n^k)$ can be approximated by formulas $\{F_n\}^{\infty}_{n=1}$ of subexponential size $2^{O(n^{2/c})}$ with subexponenital advantage: $P_{x\in \{0,1\}^n}[F_n(x)=f(x)]\geq 1/2+1/2^{O(n^{2/c})}$. Unconditionally, $V^0$ cannot prove that for sufficiently large $n$ SAT does not have circuits of size $n^{\log n}$. The proof is based on an interpretation of Krajicek's proof (2011) that certain NW-generators are hard for $T_{PV}$, the true universal theory in the language containing names for all p-time algorithms.Fri, 24 May 2013 17:44:34 +0300https://eccc.weizmann.ac.il/report/2013/077