Amplifying Lower Bounds by Means of Self-Reducibility

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+\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 NC^1. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC^0 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 TC^0 circuit family recognizing BFE has size n^{1+\epsilon}, then it would follow that TC^0 \not= \NC^1. 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.

1. Introduction

There is a great deal of pessimism in the research community, regarding the likelihood of proving superpolynomial lower bounds on the circuit size required for various computational problems. One goal of this paper is to suggest that there might be some reason to be more optimistic about prospects for circuit size lower bounds; we show that superpolynomial bounds would follow as a consequence of some very modest-sounding lower bound results (such as a lower bound of size ). Of course, a confirmed pessimist would say that this is merely evidence that even these modest-sounding lower bounds are likely to remain beyond our reach. In Section 6 we discuss some possible interpretations of our results; in particular, we discuss the extent to which it might be possible to hope that the observations we present here point to a path around the obstacles to proving circuit lower bounds that were presented by Razborov and Rudich in their work on Natural Proofs [15].