Browse Prior Art Database

On Solving Hard Problems by Polynomial-Size Circuits

IP.com Disclosure Number: IPCOM000128012D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 10 page(s) / 30K

Publishing Venue

Software Patent Institute

Related People

Dung T. I-Iuynh: AUTHOR [+3]

Abstract

This paper introduces the notions of immunity, complexity core, and Church-randomness for the non-uniform complexity class of languages accepted by polynomial-size circuit families, usually denoted as P/ Poly. While it is n,' known whether DTI1Ml(2x' 'y) is contained in P/ Poly. we show that there exist la.^._:..:~es m EXSPACE that have the property of being immune, or having dense com^ex3ty core, or being Church-random with respect to the class Pi Poly. Proofs of these results are based on techniques in generalized tiolmogorov complexity theory.

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

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

On Solving Hard Problems by Polynomial-Size Circuits

Dung T. I-Iuynh Iowa State University Computer Science Department Ames, Iowa 50011

TR 85-24

September 1985

Abstract.

This paper introduces the notions of immunity, complexity core, and Church-randomness for the non-uniform complexity class of languages accepted by polynomial-size circuit families, usually denoted as P/ Poly. While it is n,' known whether DTI1Ml(2x' 'y) is contained in P/ Poly. we show that there exist la.^._:..:~es m EXSPACE that have the property of being immune, or having dense com^ex3ty core, or being Church-random with respect to the class Pi Poly. Proofs of these results are based on techniques in generalized tiolmogorov complexity theory.

Key words. Boolean circuit, computational complexity. complexity core. Kolmogorov com- plexity, hardness, randomness, language, immunity.

1. Introduction

The hardness and randomness of languages have been investigated extensively in the literature on computational complexity. In [Lyn], Lynch introduced the notion of a poly-nomial complexity core. A language L not in P is sari to have a polynomial complexity core K if any Turing machine acceptor for L requires a non-polynomial number of steps on all except at most finitely many instances in K. Recently, a number of results concerning the existence and density of (more general) complexity cores for various complexity classes have been obtained. (Cf. [D-B]. [ESY]. [Hul]. [O-S).) On the other hand, several approaches for studying the randomness of infinite binary sequences and languages have been investigated. In [KoK], one can find different notions of pseudo-random sequences, whereas [Wlb), [Hu2], [Hu3j are concerned with the random-ness of hard languages. Church's approach has been followed in [Wlb), and [Hu3j has applied the idea of the generalized Kolmogorov complexity (cf. [Har], [KoKj, [Sip]). Results along these lines of research are concerned with the hardness and randomness of a language with respect to uniform complexity classes, especially the class P. In con-trast to this, researchers in cryptography frequently assume the intractability of several number-theoretic problems with respect to polynomial-size (Boolean) circuits, which are a non-uniform complexity measure (cf. [B-M]. [Yao)). To the author's knowledge, there are at present no complexity-theoretic results concerning the hardness (e.g. existence and den-sity of complexity cores) and randomness of languages with respect to non-uniform com-plexity classes. in particular the class of languages accepted by polynomial-size circuit families (denoted by Karp & Lipton.as P/ Poly). The present paper provides several results in this direction. It is well known that the currently lowest uniform complexity class which is provably intractable with respect to

(Equation Omitted)

Iowa State University Page 1 Dec 31, 1985

Page 2 of 10

On Solving Hard Problem...