Počet záznamů: 1
Circuit lower bounds in bounded arithmetics
- 1.
SYSNO ASEP 0438367 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Circuit lower bounds in bounded arithmetics Tvůrce(i) Pich, Ján (MU-W) SAI, ORCID Zdroj.dok. Annals of Pure and Applied Logic. - : Elsevier - ISSN 0168-0072
Roč. 166, č. 1 (2015), s. 29-45Poč.str. 17 s. Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova bounded arithmetic ; circuit lower bounds Vědní obor RIV BA - Obecná matematika CEP IAA100190902 GA AV ČR - Akademie věd UT WOS 000345480600002 EID SCOPUS 84908372074 DOI https://doi.org/10.1016/j.apal.2014.08.004 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2015
Počet záznamů: 1