0438367 - MÚ 2015 RIV NL eng J - Journal Article
Pich, Ján
Circuit lower bounds in bounded arithmetics.
Annals of Pure and Applied Logic. Roč. 166, č. 1 (2015), s. 29-45. ISSN 0168-0072. E-ISSN 1873-2461
R&D Projects: GA AV ČR IAA100190902
Keywords : bounded arithmetic * circuit lower bounds
Subject RIV: BA - General Mathematics
Impact factor: 0.582, year: 2015 ; AIS: 0.691, rok: 2015
Result website:
http://www.sciencedirect.com/science/article/pii/S0168007214000888DOI: https://doi.org/10.1016/j.apal.2014.08.004

We prove that T-Nc(1), the true universal first-order theory in the language containing names for all uniform NC1 algorithms, cannot prove that for sufficiently large n, SAT is not computable by circuits of size n(4kc) where k >= 1, c >= 2 unless each function f is an element of SIZE(n(k)) can be approximated by formulas {Fn}(n=1)(infinity) of subexponential size 2(O(n1/c)) with subexponential advantage: P-x is an element of(0,1)(n) (F-n(x) = f(x)) >= 1/2+1/2(O)(n(1/c)). Unconditionally, V cannot prove that for sufficiently large n, SAT does not have circuits of size n(logn). The proof is based on an interpretation of Krajicek's proof (Krajicek, 2011 [15]) that certain NW-generators are hard for T-PV, the true universal theory in the language containing names for all p-time algorithms.
Permanent Link: http://hdl.handle.net/11104/0241791