Circuit-size Lower Bounds and Non-reducibility to Sparse Sets

Abstract

As remarked in Cook (1980), we do not know any nonlinear lower bound on the circuit-size of a language in P or even in NP. The best known lower bound seems to be due to Paul (1975). In this paper we show that first for each nonnegative integer k, there is a language Lk in Σ2∩π2 (of Meyer and Stockmeyer (1972) hierarchy) which does not have 0(n^k)-size circuits. Using the same techniques, one is able to prove several similar results. For example, we show that for each nonnegative integer k, there is a language Lk in NP that does not have 0(n^k)-size uniform circuits. This follows as a corollary of a stronger result shown in the paper. Finally, we note that existence of "small circuits" is in suitable contexts equivalent to being reducible to sparse sets. Using this, we are able to prove for example that for any time-constructible super-polynomial function f(n), NTIME(f(n)) contains a language which is not many-to-one p-time reducible to any sparse set.