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

Original language | English (US) |
---|---|

Article number | 14 |

Journal | Journal of the ACM |

Volume | 57 |

Issue number | 3 |

DOIs | |

State | Published - Mar 1 2010 |

## All Science Journal Classification (ASJC) codes

- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence

## Keywords

- Circuit complexity
- Lower bounds
- Natural proofs
- Self-reducibility
- Time-space tradeoffs