Circuit lower bounds in bounded arithmetics

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F15%3A00438367" target="_blank" >RIV/67985840:_____/15:00438367 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/15:10317954

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.apal.2014.08.004" target="_blank" >http://dx.doi.org/10.1016/j.apal.2014.08.004</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.apal.2014.08.004" target="_blank" >10.1016/j.apal.2014.08.004</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Circuit lower bounds in bounded arithmetics

Popis výsledku v původním jazyce

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 provethat 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.

Název v anglickém jazyce

Circuit lower bounds in bounded arithmetics

Popis výsledku anglicky

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 provethat 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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/IAA100190902" target="_blank" >IAA100190902: Matematická logika, složitost a algoritmy</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Annals of Pure and Applied Logic

ISSN

0168-0072

e-ISSN

—

Svazek periodika

166

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

17

Strana od-do

29-45

Kód UT WoS článku

000345480600002

EID výsledku v databázi Scopus

—