Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR22-134 | 25th September 2022 23:40

#### Some Games on Turing Machines and Power from Random Strings

Revision #1
Authors: Alexey Milovanov, Greg McLellan
Accepted on: 25th September 2022 23:40
Keywords:

Abstract:

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.

### Paper:

TR22-134 | 23rd September 2022 17:58

#### Some Games on Turing Machines and Power from Random Strings

TR22-134
Authors: Greg McLellan, Alexey Milovanov
Publication: 25th September 2022 09:21
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint