Large Sets in AC(Exp 0): A Kolmogorov Complexity Related Property and SomeApplications

摘要

If A is a set in AC(exp 0) such that for some q greater than 0 and infinitelymany n, absolute value of (A(exp n)) is greater than 2(exp(n-log(sup q)n)), then A contains more than quasipolynomially many strings with polynomial-time bounded length-conditioned Kolmogorov complexity below n(exp epsilon), for arbitrary epsilon greater than 0, at each length n where A satisfies the above density condition. As a consequence, we exhibit a set in NP that is bi-immune to sets in AC(exp 0) that satisfy the above density condition.