Number of the records: 1  

Circuit lower bounds in bounded arithmetics

  1. 1.
    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
    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.
    Permanent Link: http://hdl.handle.net/11104/0241791

     
    FileDownloadSizeCommentaryVersionAccess
    Pich.pdf4498.2 KBPublisher’s postprintrequire
     
Number of the records: 1  

  This site uses cookies to make them easier to browse. Learn more about how we use cookies.