<p>I think the question being asked here is roughly "<strong>is there a sense in which we can replace the sequence of random bits in an algorithm with bits drawn deterministically from an appropriately long Kolmogorov random string?</strong>" This is at least the question I will attempt to answer! (The short answer is "Yes, but only if you amplify the error probability first")</p>

<hr>

<h2>Yes...</h2>

<p>We can certainly say something here. Let $L$ be some language and let $A$ be an algorithm which takes as input $x$ and a random string $r\in U_{f(|x|)}$ (the uniform distribution over $\{0,1\}^{f(|x|)}$) s.t. $\Pr[A(x,r)=L(x)]&gt;1-\epsilon(x)$. In other words, $A$ is an algorithm which errs with probability at most $\epsilon(\cdot)$.</p>

<p>Notice now that if $A$ gives the wrong answer on $(x,r)$ ie, $A(x,r)\not=L(x)$, this gives us some means of describing $r$, in particular, we can describe it as the $i$-th string which causes $A$ to err on $x.$ To do this, we simply make the machine which has hard-coded $x$, $A$, $i$, and a bit $b=1\iff x\in L$, and simply enumerates choices of $r'$ from $\{0,1\}^{f(|x|)}$ until it finds the $i$-th choice of $r'$ such that $A(x,r')\not= b$.</p>

<p>So now that we know we can leverage being a bad choice of random string into a description, let's observe some conditions which are sufficient for turning our description of $r$ into a compression. To describe $r$, we require enough bits to describe $x$, $i$, $b$, and then the code for our procedure (the code for $A$ and the routine we described), giving as a description of length $$|x|+|i|+O(1)=|x|+\log_2(2^{f(|x|)}\epsilon(x))+O(1)=|x|+f(|x|)-\log(1/\epsilon(x))+O(1).$$</p>

<p>Recall that $r$ is length $f(|x|)$, so this is a compression of $r$ if $$\log(1/\epsilon(x)) = |x|+\omega(1),$$ for example, when $\epsilon(x)=1/2^{2|x|}$. </p>

<p>Finally, observe that if $r$ were a Kolmogorov random string, then we could have no such compression, so as long as the error probability of $A$ is sufficiently small, a Kolmogorov random string in place of the sequence of random bits will cause $A$ to answer correctly!</p>

<p>Notice that the only thing we leverage about $A$ is that its error probability is small. We don't care if $A$ has an extremely long run time or if $A$ has one or two sided error.</p>

<p>Bringing this back to the question of $RP$ (or $coRP$ or $BPP$), this says that as long as we amplify the error probability of our algorithms, we can use Kolmogorov random strings in place of their random bits.</p>

<hr>

<h2>...But only if we amplify first.</h2>

<p>A followup question may be "can I do this without amplifying the error probability?" Consider the following algorithm $A$ which decides $\{0,1\}^*$ and has error probability $1/2^n$.</p>

<p>On input $x$:</p>

<ul>
<li>Generate a string $r\in\{0,1\}^n$</li>
<li>If $r=x$, reject.</li>
<li>Accept.</li>
</ul>

<p>Notice that for every choice of $r$, there is some choice of $x$ such that $A$ errs on $x$, namely the choice of $r$ that <em>is</em> $x$, so we can not replace the random sequence of bits used by $A$ with a Kolmogorov random string without amplifying it's error probability!</p>

<hr>

<p>A note about the source: I'm not sure if any of this is novel, but I included the first argument in my writeup for my qualifying exam which will eventually be available online after I finish revising it.</p>

CC BY-SA 3.0
2017-04-03T17:02:34.870Z
My friend Preetum pointed out the silliness of encoding the machine $M$ and deciding $M(x)$ when we can instead just encode a bit which says whether or not $x\in L$. I'll edit the answer to reflect this.
Dylan McKay
CC BY-SA 3.0
2017-04-03T23:20:18.270Z
Mike Sipser used a similar kind of compression argument in his cool paper https://www.sciencedirect.com/science/article/pii/0022000088900359 (note that the expander graphs he needs have indeed been explicitly constructed https://dl.acm.org/citation.cfm?id=273915)
Ryan Williams
CC BY-SA 3.0
2017-04-03T01:00:21.963Z
2017-04-03T19:13:13.427Z
2017-04-03T19:13:13.427Z
Dylan McKay
<p>Have there been any attempts to show that <a href="https://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogorov_randomness" rel="noreferrer">Kolmogorov randomness</a> would be sufficient for <a href="https://en.wikipedia.org/wiki/RP_(complexity)" rel="noreferrer">RP</a>? Would the probability used in the statement "If the correct answer is YES, then it (the probabilistic Turing machine) returns YES with probability ..." be always well defined in that case? Or would there only be upper and lower bounds for that probability? Or would there only always be some probabilistic Turing machine, for which the probabilities would be well defined (or at least the lower bound which should be bigger than 1/2)?</p>

<p>The class RP here is relatively arbitrary, and one could also ask this question for weaker notions of (pseudo-)randomness than Kolmogorov randomness. But Kolmogorov randomness seems to be a good starting point.</p>

<hr>

<p>Making sense of the word "probability" would be part of an attempt to show that Kolmogorov randomness works for RP. However, let me try to describe one possible approach, to clarify what it could mean, and why I talked about upper and lower bounds:</p>

<p>Let $s$ be a (Kolmogorov random) string. Let $A$ be a the given probabilistic Turing machine corresponding to a language from RP. Run $A$ with $s$ as source for random bits $n$ times, continuing to consume previously unconsumed bits from $s$ one after the other.</p>

<p>For $p_n^s:=\frac{\text{#YES result in first $n$ runs of $A$ on $s$}}{n}$, let $p_+^s:=\limsup_{n\to\infty}p_n^s$ and $p_-^s:=\liminf_{n\to\infty}p_n^s$. Observe that $p_+^s$ and $p_-^s$ are well defined for a given string $s$, even if it would not be random. But one may wonder whether $p_+^s=p_-^s$ in case $s$ is Kolmogorov random, or whether $p_-^{s_1}=p_-^{s_2}$ for two arbitrary Kolmogorov random strings $s_1$ and $s_2$. Or whether there exists a $p\geq 1/2$ such that $p\leq p_-^s$ for any Kolmogorov random string $s$.</p>

CC BY-SA 3.0
2017-01-07T16:20:06.467Z
I don't understand the question. What do you mean by "<concept of randomness> is sufficient for <complexity class>"? RP can be derandomized in polynomial time with an oracle for a Kolmogorov random string, if that's what you are asking.
Emil Jeřábek
CC BY-SA 3.0
2017-01-07T16:24:52.710Z
@EmilJeřábek If an "oracle for a Kolmogorov random string" is what I guess it is, then this is even more than I asked for. I just wanted to know whether RP would work with a Kolmogorov random string instead of a true random string, without the additional requirement that it would have a guarantee to always stop in polynomial time in that case (which it didn't have for the true random string).
Thomas Klimpel
CC BY-SA 3.0
2017-01-07T19:17:07.903Z
I don’t understand what you mean by saying that RP would “work”, and I don’t understand your last comment (RP machines do always stop after polynomially many steps, either by definition, or without loss of generality if using an inconvenient definition).
Emil Jeřábek
CC BY-SA 3.0
2017-01-07T19:22:07.770Z
In the question itself, I also don’t understand what you mean by “probability” when talking about Kolomogorov random strings. Unlike usual “random strings”, which are drawn from a random distribution, being Kolmogorov random is an actual yes–no property that a given string does or does not have. So, whether such a string makes an algorithm accept is not a random variable, and as such it is meaningless to ask about its probability.
Emil Jeřábek
CC BY-SA 3.0
2017-01-07T19:59:15.807Z
@EmilJeřábek I added an example what could be meant by "probability" to the question. In my comment, what I meant by "additional requirement that it would have a guarantee to always stop in polynomial time" was to stop with the correct answer (after consuming bits from a random string). It was an attempt to highlight the difference between derandomization and what I was asking for.
Thomas Klimpel
CC BY-SA 3.0
2017-01-09T06:50:18.333Z
A reasonable approach to this is to take the "constructive Martingales" perspective of algorithmically-random strings. In particular, one might hope that if $s$ fails to fool $A$, then this would translate into a "next-bit predictor" for $s$, and then into a betting strategy demonstrating that $s$ is not random. I don't know whether this approach, even if it works, would give meaningful convergence rates for $p_+$ and $p_-$; however, apparently there is an older approach to studying complexity classes (keywords: "resource-bounded measure") that uses this idea, so there is some hope.
Andrew Morgan
CC BY-SA 3.0
2017-01-09T06:53:33.267Z
Relevant Wikipedia links (which have further references) for my previous comment: [constructive Martingales](https://en.wikipedia.org/wiki/Algorithmically_random_sequence#Three_equivalent_definitions) (see third definition), and [resource-bounded measure](https://en.wikipedia.org/wiki/Resource_bounded_measure)
Andrew Morgan
CC BY-SA 3.0
2017-01-10T18:25:32.193Z
@AndrewMorgan, agreed - more concretely, if $A$'s behavior on $s$ differs from that on a truly random string, then $s$ is not algorithmically random. The only barrier is that this would be an asymptotic statement, e.g. the asymptotic proportion of time that $A$ accepts $x$ when re-run over and over on consecutive bits of $s$. But the annoying part seems to be the "asymptotic" portion...
usul
<randomized-algorithms><randomness><pseudorandomness>
Can true randomness (provably) be replaced with Kolmogorov randomness for RP?
Thomas Klimpel
# Can true randomness (provably) be replaced with Kolmogorov randomness for RP?

(Asked by: username_0 on 2017-01-07)

Have there been any attempts to show that [Kolmogorov randomness](https://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogorov_randomness) would be sufficient for [RP](https://en.wikipedia.org/wiki/RP_(complexity))? Would the probability used in the statement "If the correct answer is YES, then it (the probabilistic Turing machine) returns YES with probability ..." be always well defined in that case? Or would there only be upper and lower bounds for that probability? Or would there only always be some probabilistic Turing machine, for which the probabilities would be well defined (or at least the lower bound which should be bigger than 1/2)?

The class RP here is relatively arbitrary, and one could also ask this question for weaker notions of (pseudo-)randomness than Kolmogorov randomness. But Kolmogorov randomness seems to be a good starting point.

---

Making sense of the word "probability" would be part of an attempt to show that Kolmogorov randomness works for RP. However, let me try to describe one possible approach, to clarify what it could mean, and why I talked about upper and lower bounds:

Let $s$ be a (Kolmogorov random) string. Let $A$ be a the given probabilistic Turing machine corresponding to a language from RP. Run $A$ with $s$ as source for random bits $n$ times, continuing to consume previously unconsumed bits from $s$ one after the other.

For $p\_n^s:=\frac{\text{#YES result in first $n$ runs of $A$ on $s$}}{n}$, let $p\_+^s:=\limsup\_{n\to\infty}p\_n^s$ and $p\_-^s:=\liminf\_{n\to\infty}p\_n^s$. Observe that $p\_+^s$ and $p\_-^s$ are well defined for a given string $s$, even if it would not be random. But one may wonder whether $p\_+^s=p\_-^s$ in case $s$ is Kolmogorov random, or whether $p\_-^{s\_1}=p\_-^{s\_2}$ for two arbitrary Kolmogorov random strings $s\_1$ and $s\_2$. Or whether there exists a $p\geq 1/2$ such that $p\leq p\_-^s$ for any Kolmogorov random string $s$.

**Tags:** randomized-algorithms, randomness, pseudorandomness

> **Comments:**
> **username_1**: I don't understand the question. What do you mean by "<concept of randomness> is sufficient for <complexity class>"? RP can be derandomized in polynomial time with an oracle for a Kolmogorov random string, if that's what you are asking.  
> **username_0**: @EmilJeřábek If an "oracle for a Kolmogorov random string" is what I guess it is, then this is even more than I asked for. I just wanted to know whether RP would work with a Kolmogorov random string instead of a true random string, without the additional requirement that it would have a guarantee to always stop in polynomial time in that case (which it didn't have for the true random string).  
> **username_1**: I don’t understand what you mean by saying that RP would “work”, and I don’t understand your last comment (RP machines do always stop after polynomially many steps, either by definition, or without loss of generality if using an inconvenient definition).  
> **username_1**: In the question itself, I also don’t understand what you mean by “probability” when talking about Kolomogorov random strings. Unlike usual “random strings”, which are drawn from a random distribution, being Kolmogorov random is an actual yes–no property that a given string does or does not have. So, whether such a string makes an algorithm accept is not a random variable, and as such it is meaningless to ask about its probability.  
> **username_0**: @EmilJeřábek I added an example what could be meant by "probability" to the question. In my comment, what I meant by "additional requirement that it would have a guarantee to always stop in polynomial time" was to stop with the correct answer (after consuming bits from a random string). It was an attempt to highlight the difference between derandomization and what I was asking for.  
> **username_2**: A reasonable approach to this is to take the "constructive Martingales" perspective of algorithmically-random strings. In particular, one might hope that if $s$ fails to fool $A$, then this would translate into a "next-bit predictor" for $s$, and then into a betting strategy demonstrating that $s$ is not random. I don't know whether this approach, even if it works, would give meaningful convergence rates for $p_+$ and $p_-$; however, apparently there is an older approach to studying complexity classes (keywords: "resource-bounded measure") that uses this idea, so there is some hope.  
> **username_2**: Relevant Wikipedia links (which have further references) for my previous comment: [constructive Martingales](https://en.wikipedia.org/wiki/Algorithmically_random_sequence#Three_equivalent_definitions) (see third definition), and [resource-bounded measure](https://en.wikipedia.org/wiki/Resource_bounded_measure)  
> **username_3**: @AndrewMorgan, agreed - more concretely, if $A$'s behavior on $s$ differs from that on a truly random string, then $s$ is not algorithmically random. The only barrier is that this would be an asymptotic statement, e.g. the asymptotic proportion of time that $A$ accepts $x$ when re-run over and over on consecutive bits of $s$. But the annoying part seems to be the "asymptotic" portion...  

---

## 1 answers

### Answer by username_4 on 2017-04-03. Score: 13

I think the question being asked here is roughly "**is there a sense in which we can replace the sequence of random bits in an algorithm with bits drawn deterministically from an appropriately long Kolmogorov random string?**" This is at least the question I will attempt to answer! (The short answer is "Yes, but only if you amplify the error probability first")

---

## Yes...

We can certainly say something here. Let $L$ be some language and let $A$ be an algorithm which takes as input $x$ and a random string $r\in U\_{f(|x|)}$ (the uniform distribution over $\{0,1\}^{f(|x|)}$) s.t. $\Pr[A(x,r)=L(x)]>1-\epsilon(x)$. In other words, $A$ is an algorithm which errs with probability at most $\epsilon(\cdot)$.

Notice now that if $A$ gives the wrong answer on $(x,r)$ ie, $A(x,r)\not=L(x)$, this gives us some means of describing $r$, in particular, we can describe it as the $i$-th string which causes $A$ to err on $x.$ To do this, we simply make the machine which has hard-coded $x$, $A$, $i$, and a bit $b=1\iff x\in L$, and simply enumerates choices of $r'$ from $\{0,1\}^{f(|x|)}$ until it finds the $i$-th choice of $r'$ such that $A(x,r')\not= b$.

So now that we know we can leverage being a bad choice of random string into a description, let's observe some conditions which are sufficient for turning our description of $r$ into a compression. To describe $r$, we require enough bits to describe $x$, $i$, $b$, and then the code for our procedure (the code for $A$ and the routine we described), giving as a description of length $$|x|+|i|+O(1)=|x|+\log\_2(2^{f(|x|)}\epsilon(x))+O(1)=|x|+f(|x|)-\log(1/\epsilon(x))+O(1).$$

Recall that $r$ is length $f(|x|)$, so this is a compression of $r$ if $$\log(1/\epsilon(x)) = |x|+\omega(1),$$ for example, when $\epsilon(x)=1/2^{2|x|}$.

Finally, observe that if $r$ were a Kolmogorov random string, then we could have no such compression, so as long as the error probability of $A$ is sufficiently small, a Kolmogorov random string in place of the sequence of random bits will cause $A$ to answer correctly!

Notice that the only thing we leverage about $A$ is that its error probability is small. We don't care if $A$ has an extremely long run time or if $A$ has one or two sided error.

Bringing this back to the question of $RP$ (or $coRP$ or $BPP$), this says that as long as we amplify the error probability of our algorithms, we can use Kolmogorov random strings in place of their random bits.

---

## ...But only if we amplify first.

A followup question may be "can I do this without amplifying the error probability?" Consider the following algorithm $A$ which decides $\{0,1\}^\*$ and has error probability $1/2^n$.

On input $x$:

* Generate a string $r\in\{0,1\}^n$
* If $r=x$, reject.
* Accept.

Notice that for every choice of $r$, there is some choice of $x$ such that $A$ errs on $x$, namely the choice of $r$ that *is* $x$, so we can not replace the random sequence of bits used by $A$ with a Kolmogorov random string without amplifying it's error probability!

---

A note about the source: I'm not sure if any of this is novel, but I included the first argument in my writeup for my qualifying exam which will eventually be available online after I finish revising it.

> **Comments:**
> **username_4**: My friend Preetum pointed out the silliness of encoding the machine $M$ and deciding $M(x)$ when we can instead just encode a bit which says whether or not $x\in L$. I'll edit the answer to reflect this.  
> **username_5**: Mike Sipser used a similar kind of compression argument in his cool paper https://www.sciencedirect.com/science/article/pii/0022000088900359 (note that the expander graphs he needs have indeed been explicitly constructed https://dl.acm.org/citation.cfm?id=273915)  

---

