Title :
Almost everywhere high nonuniform complexity
Author_Institution :
Dept. of Comput. Sci., Iowa State Univ., Ames, IA, USA
Abstract :
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
Keywords :
computational complexity; decidable; exponential space; exponential-time; nonuniform complexities; program-size complexity; pseudorandom sequences; uniform complexity classes; Binary sequences; Boolean functions; Circuits; Computer science; Lifting equipment; Polynomials; Size measurement; Time factors; Time measurement; Upper bound;
Conference_Titel :
Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual
Conference_Location :
Eugene, OR
Print_ISBN :
0-8186-1958-9
DOI :
10.1109/SCT.1989.41813