11
$\begingroup$

Have there been any attempts to show that Kolmogorov randomness would be sufficient for RP? 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$.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jan 7 '17 at 16:20
  • 2
    $\begingroup$ 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). $\endgroup$ – Emil Jeřábek Jan 7 '17 at 19:17
  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jan 7 '17 at 19:22
  • 1
    $\begingroup$ 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. $\endgroup$ – Andrew Morgan Jan 9 '17 at 6:50
  • 1
    $\begingroup$ Relevant Wikipedia links (which have further references) for my previous comment: constructive Martingales (see third definition), and resource-bounded measure $\endgroup$ – Andrew Morgan Jan 9 '17 at 6:53
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dylan McKay Apr 3 '17 at 17:02
  • 1
    $\begingroup$ Mike Sipser used a similar kind of compression argument in his cool paper sciencedirect.com/science/article/pii/0022000088900359 (note that the expander graphs he needs have indeed been explicitly constructed dl.acm.org/citation.cfm?id=273915) $\endgroup$ – Ryan Williams Apr 3 '17 at 23:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.