Browse Prior Art Database

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

IP.com Disclosure Number: IPCOM000128139D
Original Publication Date: 1981-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 14 page(s) / 38K

Publishing Venue

Software Patent Institute

Related People

R. Kannan: AUTHOR [+3]

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 kj

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

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

R. Kannan Department of Mathematics Massachusetts Institute of Technology

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 kj

there is a language L k in Z 2 (17T 2 (of Meyer and Stockmeyer (1972) .k hierarchy) which does 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 k in NP that does not have O(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.

1
1. Introduction

A circuit for us is a Boolean circuit containing AND, OR and NEGATION gates with fan-in and fan-out of at most 2. (We remark that since all the results are proved for all polynomials, they are not changed if we allow arbitrary fan-out or allow other gates - for example EXCLUSIVE OR etc. because under these changes circuit-size as defined below changes by at most a polynomial (see Savage (1976)). The circuit-size s(C) of a circuit C is the number of gates in the circuit. Clearly, there are constants k 0

and k such that every circuit of size s can be encoded into a

(Equation Omitted)

We let P as usual denote the class of languages accepted by a multitape Turing machine in polynomial-time. E i Or i ) is the class of languages accepted in polynomial-time by machines with i alternations beginning with an existential (universal) guess. (Kozen (1976) and Chandra and Stockmeyer (1976)).

A family of circuits {C is said to accept a language n n=l L over {0,11 if for each n, C n is an n- input circuit whose output is 1 for precisely the n-length strings of L(O for other n-length strings). We say that a language L has 0(f(n)) circuits if

1 Supported by NSF Grants MCS-8105557 and MCS-77-09906

Massachusetts Institute of Technology Page 1 Dec 31, 1981

Page 2 of 14

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

{C 00 accepts L and there is,a constant k such that s(C )gkf(n) n n=1 n for all but finitely many n. A language has small circuits if it has 0(n k )-size circuits for some fixed k. A class of languages has small circuits if every member of it does. If one can show that some language L in NP (or that in fact

(Equation Omitted)

for some I) does not have small circuits, then we would have proved that

(Equation Omitted)

. (since p does have small...