Revision #1 Authors: Alexey Milovanov, Greg McLellan

Accepted on: 25th September 2022 23:40

Downloads: 221

Keywords:

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.

TR22-134 Authors: Greg McLellan, Alexey Milovanov

Publication: 25th September 2022 09:21

Downloads: 247

Keywords:

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.