Amplifying lower bounds by means of self-reducibility
Open Access
- 29 March 2010
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 57 (3) , 1-36
Abstract
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+ϵ for every ϵ> 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+ϵ d . If one were able to improve this lower bound to show that there is some constant ϵ> 0 (independent of the depth d ) such that every TC 0 circuit family recognizing BFE has size at least n 1+ϵ , then it would follow that TC 0 ≠ NC 1 . We show that proving lower bounds of the form n 1+ϵ is not ruled out by the Natural Proof framework of Razborov and Rudich and hence there is currently no known barrier for separating classes such as ACC 0 , TC 0 and NC 1 via existing “natural” approaches to proving circuit lower bounds. We also show that problems with small uniform constant-depth circuits have algorithms that simultaneously have small space and time bounds. We then make use of known time-space tradeoff lower bounds to show that SAT requires uniform depth d TC 0 and AC 0 [6] circuits of size n 1+ c for some constant c depending on d .Keywords
Funding Information
- Ministry of Education, Youth and Sports (GAČR 201/07/P276P202/10/0854)
- GAAVČR (IAA100190902)
- Division of Computing and Communication Foundations (CCF-05147093, CCF-0514155DMS-0652582CCF-0830133CCF-0832787)
This publication has 39 references indexed in Scilit:
- Time-space trade-off lower bounds for randomized computation of decision problemsJournal of the ACM, 2003
- Time–Space Tradeoffs for SatisfiabilityJournal of Computer and System Sciences, 2000
- Natural ProofsJournal of Computer and System Sciences, 1997
- Counting Quantifiers, Successor Relations, and Logarithmic SpaceJournal of Computer and System Sciences, 1997
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmeticIzvestiya: Mathematics, 1995
- On uniformity within NC1Journal of Computer and System Sciences, 1990
- Bounded-width polynomial-size branching programs recognize exactly those languages in NC1Journal of Computer and System Sciences, 1989
- Short propositional formulas represent nondeterministic computationsInformation Processing Letters, 1988
- Unbounded fan-in circuits and associative functionsJournal of Computer and System Sciences, 1985
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984