On solving hard problems by polynomial-size circuits
type: Item
instance of: scholarly article
title: On solving hard problems by polynomial-size circuits
zbMATH Open document ID: 0632.68046
DOI: 10.1016/0020-0190(87)90181-5
author: Dung T. Huynh
published in: Information Processing Letters
publication date: 1987-01-01T00:00:00Z
review text: This paper introduces the notions of immunity, complexity core, and Church-randomness for the nonuniform complexity class of languages accepted by polynomial-size circuit families, usually denoted as P/Poly. While it is not known whether \(DTIME(2^{poly})\) is contained in P/Poly, we show that there exist languages in EXSPACE that have the property of being immune, or having dense complexity core, or being Church-random with respect to the class P/Poly. Proofs of these results are based on techniques in generalized Kolmogorov complexity theory.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 4028902
zbMATH Keywords: Boolean circuit
zbMATH Keywords: hardness
zbMATH Keywords: immunity
zbMATH Keywords: complexity core
zbMATH Keywords: Church-randomness
zbMATH Keywords: complexity class
zbMATH Keywords: languages accepted by polynomial-size circuit families
zbMATH Keywords: Kolmogorov complexity
MaRDI profile type: Publication
full work available at URL: 0020-0190(87)90181-5
OpenAlex ID: W1977590950
cites work: Bi-immune sets for complexity classes
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
cites work: On the Length of Programs for Computing Finite Binary Sequences
cites work: Hard-core theorems for complexity classes
cites work: Some Observations about the Randomness of Hard Problems
cites work: Q3751001
cites work: Circuit-size lower bounds and non-reducibility to sparse sets
cites work: On Reducibility to Complex or Sparse Sets
cites work: Q3219763
Recommended article: Q3123054
Recommended article: Q4015003
Recommended article: A note on dimensions of polynomial size circuits
Recommended article: Q4638059
Recommended article: Q4601837
Recommended article: On Threshold Circuits and Polynomial Computation
Recommended article: On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy
Recommended article: Q3976040
Recommended article: Q5368903
Recommended article: On the bit complexity of polynomial system solving
description: scientific article; zbMATH DE number 4028902