We consider sets of strings with high Kolmogorov complexity, mainly in resource-bounded settings but also in the traditional recursion-theoretic sense. We present efficient reductions, showing that these sets are hard and complete for various complexity classes. In particular, in addition to the usual Kolmogorov complexity measure K, we consider the ...
more >>>