On solving hard problems by polynomial-size circuits

DOI10.1016/0020-0190(87)90181-5zbMath0632.68046OpenAlexW1977590950MaRDI QIDQ1095663

Dung T. Huynh

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90181-5

zbMATH Keywords

Kolmogorov complexityimmunityhardnessBoolean circuitcomplexity classChurch-randomnesscomplexity corelanguages accepted by polynomial-size circuit families

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Random languages for nonuniform complexity classes

Cites Work

• Unnamed Item
• Unnamed Item
• Circuit-size lower bounds and non-reducibility to sparse sets
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Bi-immune sets for complexity classes
• Some Observations about the Randomness of Hard Problems
• Hard-core theorems for complexity classes
• On Reducibility to Complex or Sparse Sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On the Length of Programs for Computing Finite Binary Sequences