Amplifying Lower Bounds by Means of Self-Reducibility

0318523 - MÚ 2009 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
Allender, E. - Koucký, Michal
Amplifying Lower Bounds by Means of Self-Reducibility.
[Zesilování dolních odhadů pomocí dolů samopřevoditelnosti.]
Proceedings of IEEE Conference on Computational Complexity 2008. Maryland: IEEE Computer Society Press, 2008, s. 31-40. ISBN 978-0-7695-3169-4.
[IEEE Conference on Computational Complexity 2008. College Park (US), 23.06.2008-26.06.2008]
Grant CEP: GA ČR GP201/07/P276
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: circuit complexity * lower bounds * natural proofs
Kód oboru RIV: BA - Obecná matematika

We observe that many important computational problems in NC1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC0 circuits if and only if it has TC0 circuits of size n(1+epsilon) for every epsilon > 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 NC1. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC0 circuits of size n(1+epsilon d). If one were able to improve this lower bound to show that there is some constant epsilon > 0 such that every TC0 circuit family recognizing BFE has size n(1+epsilon), then it would follow that TC0 not equal NC1.

Ukážeme, že mnohé výpočetní problémy ze třídy NC1 mají vlastnost nazývanou silná auto-reducibilita. S použitím této vlastnosti poté ukážeme, že problém A s touto vlasností má TC0 obvody polynomiální velikosti právě tehdy, když ma TC0 obvody velikosti n^{1+epsilon}, pro libovolně malé epsilon. Pro odseparování třídy NC1 od TC0 tak postačuje ukázat, že problém A nemá TC0 obvody velikosti řekněme n^2. Podobný typ výsledků obdržíme i pro další obvodové třídy. Dále ukážeme dolní odhad na velikost uniformních TC0 obvodů pro SAT.
Trvalý link: http://hdl.handle.net/11104/0167916