Show simple item record

dc.contributor.authorJoseph, Deborah Aen_US
dc.contributor.authorSitharam, Meeraen_US
dc.description.abstractThis 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.en_US
dc.publisherUniversity of Wisconsin-Madison Department of Computer Sciencesen_US
dc.titleKolmogorov Complexity, Restricted Nondeterminism and Generalized Spectraen_US
dc.typeTechnical Reporten_US

Files in this item


This item appears in the following Collection(s)

  • CS Technical Reports
    Technical Reports Archive for the Department of Computer Sciences at the University of Wisconsin-Madison

Show simple item record