Randomness is hard

We study the set of incompressible strings for various resource bounded ver sions of Kolmogorov complexity. The resource bounded versions of Kolmogorov complexity we study are polynomial time CD complexity defined by Sipser, t he nondeterministic variant CND due to Buhrman and Fortnow, and the polynom ial space bounded Kolmogorov complexity CS introduced by Hartmanis. For all of these measures we define the set of random strings R-t(CD), R-t(CND), a nd R-t(CS) as the set of strings x such that CDt (x), CNDt (x), and CSs (x) is greater than or equal to the length of x for s and t polynomials. We sh ow the following: . MA subset of or equal to NPtRCD, where MA is the class of Merlin Arthur g ames defined by Babai. . AM subset of or equal to NPtRCND, where AM is the class of Arthur Merlin games. . PSPACE subset of or equal to NPscRCS. In the last item cR(sCS) is the set of pairs x, y so that x is random given y. These results show that the set of random strings for various resource bounds is hard for complexity classes under nondeterministic reductions. This paper contrasts the earlier work of Buhrman and Mayordomo where they s how that for polynomial time deterministic reductions the set of exponentia l time Kolmogorov random strings is not complete for EXP.