On solving hard problems by polynomial-size circuits (Q1095663)

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.