Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Some Games on Turing Machines and Power from Random Strings

RSS-Feed




Revision #1
Authors: Alexey Milovanov, Greg McLellan
Accepted on: 25th September 2022 23:40
Downloads: 73
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
Downloads: 67
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