Levin's Completeness Result Follow presentation of [Goldreich] If is easy on average Then for every L in NP, every D computable distribution, is easy on average BH is non-deterministic Bounded Halting: given, does M(x) accept with t steps
{}