Almost everywhere high nonuniform complexity
Jack H. Lutz · 2003
Investigates the distribution of nonuniform complexities in uniform complexity classes. The author proves that almost every problem decidable in exponential space has essentially maximum circuit-size and program-size complexity almost everywhere. In exponential-time complexity classes, he proves that the strongest relativizable lower bounds hold almost everywhere for almost all problems. He shows that infinite pseudorandom sequences have high nonuniform complexity almost everywhere. The results are unified by a refined formulation of the underlying measure theory and by the introduction of a new nonuniform complexity measure, the selective program-size complexity.>