Počet záznamů: 1
Amplifying lower bounds by means of self-reducibility
- 1.
SYSNO ASEP 0352511 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 Amplifying lower bounds by means of self-reducibility Tvůrce(i) Allender, E. (US)
Koucký, Michal (MU-W) RID, SAI, ORCIDZdroj.dok. Journal of the ACM. - : Association for Computing Machinery - ISSN 0004-5411
Roč. 57, č. 3 (2010), s. 1-36Poč.str. 36 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova Circuit Complexity ; Lower Bounds ; Natural Proofs ; Self-Reducibility ; Time-Space Tradeoffs Vědní obor RIV BA - Obecná matematika CEP GAP202/10/0854 GA ČR - Grantová agentura ČR 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy IAA100190902 GA AV ČR - Akademie věd CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000277058400003 EID SCOPUS 77950344196 DOI 10.1145/1706591.1706594 Anotace We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial-size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+eps} for every eps> 0 (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields, consider the Boolean Formula Evaluation problem (BFE), which is complete for NC^1 and has the self-reducibility property. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC^0 circuits of size n^{1+eps_d} . If one were able to improve this lower bound to show that there is some constant eps> 0 (independent of the depth d) such that every TC^0 circuit family recognizing BFE has size at least n^{1+eps}, then it would follow that TC^0 /not= NC^1. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2011
Počet záznamů: 1