Some Games on Turing Machines and Powerfrom Random Strings
Alexey Milovanov

24.07.2023 / Batumi, CiE

Alexey Milovanov

Some Games on Turing Machines and Power from Ra

What is “Power from Random Strings”
Denote by KU (x) the Kolmogorov complexity of x withrespect to a universal decompressor U—the minimal lengthof a program that outputs x.
Denote by RU the oracle function that outputs KU (x) on
input x.
In the sense of computational complexity, how strong is thisoracle?
TConsider, for example, PR := U PRU . What are upper andlower bounds for this class? The same questions are arouses
for BPPR , PRtt ,. . .
Partial answers to this questions were done in works
Allender, Lempp, Hirahara, Fortnow,. . . with co-authors.

Alexey Milovanov

Some Games on Turing Machines and Power from Ra

Motivation: why should we research PR , BPPR ?..
This examination raises interesting questions in areas suchas derandomization and interactive proofs within
computational complexity.
This research can help to understand the complexity of
Minimal Circuit Size Problem (MCSP):
given the truth-table of a Boolean function f and a number
k , does there exist a Boolean circuit of size at most kcomputing f ?
Open problem: Is MCSP NP-complete?
MSCP is close to the following notion in resource-bounded
Kolmogorov complexity KT.
KT (x) := min{|p| + t : ∀i ≤ |x| + 1, ∀b ∈ {0, 1, ∗} :U(p, i, b) = 1 ⇐⇒ b = xi and U works in time t}.
Usually, problems in plain Kolmogorov complexity areeasier than the same problems in resource-bounded
Kolmogorov complexity.
Alexey Milovanov

Some Games on Turing Machines and Power from RaLower bounds ITheorem (2005;Allender, Buhrman, Koucky, van Melkebeek,Ronneburger)
PR = BPPR ;PSPACE ⊆ PR .
Idea of the proof: oracle R allows to distinguish random strings
from pseudo-random. In fact authors do not need oracle
function, they used {x |K(x) > |x|2 }.
Theorem (2006; Allender, Buhrman, Koucky)
H ∈ P/polyR ;NEXP ⊆ NPR .
Here H is the Halting problem.
The proofs used interactive proofs and KT.
Alexey Milovanov

Some Games on Turing Machines and Power from RaLower bounds II

Theorem (2010, Buhrman, Fortnow, Koucky, Loff)
BPP ⊆ PRtt . Here tt means truth-table reductions.
Theorem (2020, Hirahara)
EXPNP ⊆ PR ;NEXP ⊆ BPPRtt .
The proofs use local-decoding codes, pseudo-random generators,interactive proofs.
These proofs use oracle-function R (not just the set of randomstrings). The results are still valid if the oracle-function gives
the value with logarithmic precision.

Alexey Milovanov

Some Games on Turing Machines and Power from RaUpper bounds
Theorem (2014, M. Cai, R. Downey, R. Epstein, S. Lempp, andJ. Miller )Classes PR and NPR contains only decidable languages.
Here R is the oracle function for plain or prefix complexity.
Theorem (2013, Allender, Friedman, Gasarch)
PRtt ⊆ PSPACE;
PR , NPR ⊆ EXPSPACE.
Here R is the oracle function for prefix complexity.
The idea is to use the main theorem about prefix
complexity—its connection with universal semi-measures.
The statements above are reduced to some game on Turingmachines. The authors show that defining a winning player insuch games belongs to PSPACE/EXPSPACE. This allows (bysome reasons) to prove the upper bounds.
Alexey Milovanov

Some Games on Turing Machines and Power from RaGame for tt-reduction
Let M be a polynomial time Turing machine that hasaccess to oracle O. This machine implements tt-reduction,i.e. on inputs of length n the machine M asks poly(n)questions to oracle O. After this machine outputs 1 or 0.
Initially O is empty. Let x be some string. Consider thefollowing game. The goal of Alice is M O (x) = 1, the goal of
Bob is M O (x) = 0. Alice and Bob can add strings to O forsome cost. Specifically, adding string y costs v (y ) for somefunction v .
The players take turns, but they can skip their turn if thecurrent value M O (x) is acceptable for them. Initially Alicehas cA dollars, Bob has cB dollars.
The problem is to decide the winner by (x, cA , cB ).

Alexey Milovanov

Some Games on Turing Machines and Power from RaNew results
Theorempoly
BPPR.
tt ⊆ AEXP
poly
Here AEXP
is the class of languages decidable inexponential time by an alternating Turing machine thatswitches from an existential to a universal state or vice versa at
most polynomial times.

Theorem (Informal)
The games that appears in the proof of the following statements
RRPR
tt ⊆ PSPACE and P , NP ⊆ EXPSPACE are PSPACE- andEXPSPACE-complete.
This means that current methods can not provide better upperbounds for PR , NPR and PR
tt than known.
Alexey Milovanov

Some Games on Turing Machines and Power from RaSub-adaptive reductions
Definition
A machine M with an oracle access is called sub-adaptive if forevery input all nodes in the reduction tree (i.e., all the oraclequeries) are different.
f (a1 ) =?

114) =13) =f (a2) =f (af (a11 ) =?

f (a12 ) =?

3f (a10 ) =?

f (a4 ) = 2Alexey Milovanov

f (a9 ) =?

)=f (a 4f (a8 ) =?

3f (a7 ) =?

f (a3 ) = 2f (a3f (a4 ) =?

)=f (a 33f (a6 ) =?

)=f (a3 ) =?

)=f (a 2f (a2 ) = 2

1f (a2 ) =?

f (a5 ) =?

f(a1f (a1 ) = 2)=
a1f(f (a13 ) =?

Some Games on Turing Machines and Power from Ra

Bounds for sub-adaptive reductions

Theorem
PRsa ⊆ EXP.
Recall that for adaptive reduction the upper bound isEXPSPACE, for tt-reduction the upper bound is PSPACE.
We can consider a “mixture” of tt-reduction and sub-adaptive
reduction and also get EXP as an upper bound.
Open problem
Is there any non-trivial lower bounds for PRsa ?

Alexey Milovanov

Some Games on Turing Machines and Power from Ra

Alexey Milovanov

Some Games on Turing Machines and Power from Ra