Browse Prior Art Database

Circuit-size lower bounds and non-reducibility to sparse sets Disclosure Number: IPCOM000149089D
Original Publication Date: 1899-Dec-30
Included in the Prior Art Database: 2007-Apr-12
Document File: 48 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Kannan, R.: AUTHOR [+2]


R, Kannan

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 48

Circuit-size lower bounds and
non-reducibility to sparse sets


               R, Kannan
Department of Mathematics
Massachusetts Institute of Technology


    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 kn~~wn
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 C2nn2 (of Lleyer and Stockmeyer (1972)


hierarchy) which dsoes not have O(n )-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 L in NP that does not have O(n )-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-o:ne p-time reducible to any
sparse set..


Support;ed by NSF Grants MCS-8105557 and MCS-77-09906


[This page contains 1 picture or other non-text object]

Page 2 of 48

1. Introduction

A circuit for us is a Boolean circuit containing AND, OW

and NEGATION gates with fan-in and fan-out of a t most 2 , Ib7e remark that since all the results are proved for a l l polyromials, they are not changed if we allow arbitrary fan-out or allcw other gates - for example EXCLUSIVE OR etc, because under these changes circuit-size as defined below changes by at most a polynonial (see Savage 61976)), The circuit-size s(C) of a circuit C is the
number of gates i n the circuit, Clearly, there are constants k 0 and k such that every circuit of size s can be encoded into a
0,1 string e (C) of length a t most kg (s
(C) 1 k-

     We let P as usual denote the class of languages accepted
by a multitape Turing machine in polynomial-time. Z i ( ~ i ) is the class of languages accepted in polynomial-time by machines with
i alternations beginning w i t h an existential (universal) guess, (Kozen (1976 j. and Claandra and Stoekmeyer (1976 1 ) ,

A family of circuits {tnig=l is said to accept a language

L over 10,lI i f for each n, Cn is an n-input circuit whose output is 1 for precisely the n-Leng-th strings of LIO for sthzr n-length strings). W e say khat a language L has CB(f(n)) circuits if

- ---

{C I~
n n=l accepts L and there is a constant k such that s(C )gkf(n)

for a l l but finitely many n, A language has small circuits if it
- - ---

has O (n B-size circuits for some fixed k, A class of lang,~ages has small circuits if every member of it does, If one can show

[This page contains 1 picture or other non-text object]

Page 3 of 48

that some language I; i n NP (or in fact i n Xi for some i) does not...