Denote by $R$ the set of strings with high Kolmogorov complexity. In [E. Allender, H. Buhrman, M. Kouck\'y, D. van Melkebeek, and D. Ronneburger.
Power from random strings.
\emph{SIAM Journal on Computing}, 35:1467--1493, 2006.] the idea of using $R$ as an oracle for resource-bounded computation models was presented. This idea was later developed in several others papers.
We prove new lower bounds for $Q^R_{tt}$ and $Q^R_{sa}$:
- Oblivious-NP is subset of $Q^R_{tt}$;
- Oblivious-MA is subset of $Q^R_{sa}$.

Here $Q$ means quazi-polynomial-time; ``sa'' means sub-adaptive
reduction - a new type of reduction that we introduce. This type of reduction is not weaker than truth-table reduction and is not stronger than Turing reduction.

Also we prove upper bounds for BBP^R_{tt} and P^R_{sa} following [E. Allender, L. Friedman, and W. Gasarch. Limits on the computational power of random
strings.]:

P^R_{sa} is subset of EXP
BBP^R_{tt} is subset of AEXP(poly).

Here AEXP(poly) is the class of languages decidable in exponential time by an alternating Turing machine that switches from an existential to a universal state or vice versa at most polynomial times.

Finally we analyze some games that originate in [E. Allender, L. Friedman, and W. Gasarch. Limits on the computational power of random
strings.]. We prove completeness of these games. These results show that methods in this can not prove better upper bounds for P^R, NP^R and P^R_{tt} than known.

Denote by $R$ the set of strings with high Kolmogorov complexity. In [E. Allender, H. Buhrman, M. Kouck\'y, D. van Melkebeek, and D. Ronneburger.
Power from random strings.
\emph{SIAM Journal on Computing}, 35:1467--1493, 2006.] the idea of using $R$ as an oracle for resource-bounded computation models was presented. This idea was later developed in several others papers.
We prove new lower bounds for $Q^R_{tt}$ and $Q^R_{sa}$:
- Oblivious-NP is subset of $Q^R_{tt}$;
- Oblivious-MA is subset of $Q^R_{sa}$.

Here $Q$ means quazi-polynomial-time; ``sa'' means sub-adaptive
reduction - a new type of reduction that we introduce. This type of reduction is not weaker than truth-table reduction and is not stronger than Turing reduction.

Also we prove upper bounds for BBP^R_{tt} and P^R_{sa} following [E. Allender, L. Friedman, and W. Gasarch. Limits on the computational power of random
strings.]:

P^R_{sa} is subset of EXP
BBP^R_{tt} is subset of AEXP(poly).

Here AEXP(poly) is the class of languages decidable in exponential time by an alternating Turing machine that switches from an existential to a universal state or vice versa at most polynomial times.

Finally we analyze some games that originate in [E. Allender, L. Friedman, and W. Gasarch. Limits on the computational power of random
strings.]. We prove completeness of these games. These results show that methods in this can not prove better upper bounds for P^R, NP^R and P^R_{tt} than known.