Počet záznamů: 1
Amplifying lower bounds by means of self-reducibility
- 1.0352511 - MÚ 2011 RIV US eng J - Článek v odborném periodiku
Allender, E. - Koucký, Michal
Amplifying lower bounds by means of self-reducibility.
Journal of the ACM. Roč. 57, č. 3 (2010), s. 1-36. ISSN 0004-5411. E-ISSN 1557-735X
Grant CEP: GA ČR GAP202/10/0854; GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: Circuit Complexity * Lower Bounds * Natural Proofs * Self-Reducibility * Time-Space Tradeoffs
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 3.375, rok: 2010
http://dl.acm.org/citation.cfm?doid=1706591.1706594
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.
Trvalý link: http://hdl.handle.net/11104/0192003
Název souboru Staženo Velikost Komentář Verze Přístup Koucky.pdf 1 249.6 KB Autorský postprint vyžádat
Počet záznamů: 1