Kolmogorov Complexity, Restricted Nondeterminism and Generalized Spectra

Abstract

This paper uses the technique of generalized spectra and expressibility of complexity classes in logic, developed by Fagin and Immerman, to give alternate characterizations of specific subclasses of NP. These characterizations serve to unify concepts that appear in seemingly different areas of complexity theory; namely, the restricted nondeterminism on Kintala and Fischer and the time bounded Kolmogorov complexity of Daley and Ko. As consequences of these characterizations we show that relatively easy subsets of NP � P can not be pseudorandomly generated, unless UTME[t(n)] = DTIME[t(n)] for certain exponential functions t. Secondly, we show that no easy subset of the set of all satisfying assignments of satisfiable g(n)-easy formulas contains an assignment for each of these formulas, unless NEXPTIME = EXPTIME. The latter partially answers a question raised by Hartman�s.