Circuit lower bounds in bounded arithmetics

0438367 - MÚ 2015 RIV NL eng J - Článek v odborném periodiku
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
Grant CEP: GA AV ČR IAA100190902
Klíčová slova: bounded arithmetic * circuit lower bounds
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.582, rok: 2015
http://www.sciencedirect.com/science/article/pii/S0168007214000888

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.
Trvalý link: http://hdl.handle.net/11104/0241791