Can true randomness (provably) be replaced with Kolmogorov randomness for RP?
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)]&gt;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.