<p>There are several notions of randomness in computability theory (/the arithmetic hierarchy; lookup "Martin-Lof randomness", "Kurtz random", "Schnorr random", ...), but I think the ones that are analogous to $\mathsf{BPP}$ become trivial in the setting of the arithmetic hierarchy. The reason is essentially that a randomized Turing machine with bounded error can be simulated by a deterministic one: the deterministic one simulates the random one with all settings of the randomness and then takes the majority vote. If the original machine took time $t(n)$ then the new machine takes time $2^{t(n)}$, which is why this trick tends not to work in the resource-bounded case. </p>

<p>(Though of course it works for any deterministic time-bounded class where if time bound $t(n)$ is allowed in the class then so is $2^{t(n)}$. In particular, this trick works in $\mathsf{DTIME}(\mathcal{E}^4)$, where $\mathcal{E}^4$ is the fourth level of the <a href="http://en.wikipedia.org/wiki/Grzegorczyk_hierarchy">Grzegorczyk hierarchy</a> of primitive recursive functions. But that's still a pretty big class.)</p>

CC BY-SA 3.0
2015-12-27T23:03:46.140Z
could you please provide a reference for this?
Turbo
CC BY-SA 3.0
2015-12-28T20:56:53.280Z
@Turbo: Which "this" do you want a reference for?
Joshua Grochow
CC BY-SA 3.0
2015-12-28T20:59:57.310Z
claim that every possible notion of randomness becomes trivial and reasoning about primitive recursive functions. Actually as many references to make it self contained is good.
Turbo
CC BY-SA 3.0
2015-12-28T21:14:36.037Z
@Turbo: For computable analogues of BPP being trivial I don't know a reference, but I essentially already gave the proof in the answer. (ML, Kurtz, Schnorr, etc. randomness are not analogous to BPP.) The thing about $\mathcal{E}^4$ follows directly from the definition, which is in the linked wikipedia article. Was there something more you wanted?
Joshua Grochow
CC BY-SA 3.0
2015-12-29T00:37:00.270Z
I am just wondering is there an analogue of sipser's theorem in arithmetic hierarchy?
Turbo
CC BY-SA 3.0
2015-12-29T05:41:43.803Z
@Turbo: As far as I know, there is not, precisely because there is no (known) interesting analogue of BPP in the arithmetic hierarchy...
Joshua Grochow
CC BY-SA 3.0
2015-12-29T06:52:28.020Z
one more very very trivial problem we know P=BPP implies NEXP is not in P/poly or perm does not have poly circuits. AFAIK perm needs superpoly circuits imply NEXP is not in P/poly. So why dont we just say P=BPP implies NEXP is not in P/poly?
Turbo
CC BY-SA 3.0
2015-12-29T06:54:44.523Z
I am talking theorem 4.7 here https://books.google.com/books?id=xPAnxps5PNgC&pg=PA97&lpg=PA97&dq=p+bpp+nexp+permanent&source=bl&ots=XQD4j5W5Ic&sig=BPK6EF7jToZJeqJTaBl7YiKM4NU&hl=en&sa=X&ved=0ahUKEwi2xvLIrYDKAhVBF2MKHaCNAHEQ6AEISzAI#v=onepage&q=p%20bpp%20nexp%20permanent&f=false I am confused why you need 1 and 2?
Turbo
CC BY-SA 3.0
2015-12-30T01:48:42.390Z
@Turbo: That's a separate question.
Joshua Grochow
CC BY-SA 3.0
2015-12-30T01:51:17.937Z
http://cs.stackexchange.com/questions/51274/query-on-consequences-of-p-bpp done
Turbo
CC BY-SA 3.0
2013-11-26T23:08:39.187Z
2013-11-26T23:08:39.187Z
Joshua Grochow
<p>In the arithmetic hierarchy, is there an analog of $P$ versus $BPP$? Particularly is there a notion of randomness there?</p>

<p>If there is no such analogy, why is randomness in the resource bounded case special? Any references will be great.</p>

<cc.complexity-theory><complexity-classes><computability><randomness><derandomization>
Arithmetic Analogues of P versus BPP
Turbo
# Arithmetic Analogues of P versus BPP

(Asked by: username_0 on 2013-11-26)

In the arithmetic hierarchy, is there an analog of $P$ versus $BPP$? Particularly is there a notion of randomness there?

If there is no such analogy, why is randomness in the resource bounded case special? Any references will be great.

**Tags:** cc.complexity-theory, complexity-classes, computability, randomness, derandomization

---

## 1 answers

### Answer by username_1 on 2013-11-26. Score: 5 | Accepted answer

There are several notions of randomness in computability theory (/the arithmetic hierarchy; lookup "Martin-Lof randomness", "Kurtz random", "Schnorr random", ...), but I think the ones that are analogous to $\mathsf{BPP}$ become trivial in the setting of the arithmetic hierarchy. The reason is essentially that a randomized Turing machine with bounded error can be simulated by a deterministic one: the deterministic one simulates the random one with all settings of the randomness and then takes the majority vote. If the original machine took time $t(n)$ then the new machine takes time $2^{t(n)}$, which is why this trick tends not to work in the resource-bounded case.

(Though of course it works for any deterministic time-bounded class where if time bound $t(n)$ is allowed in the class then so is $2^{t(n)}$. In particular, this trick works in $\mathsf{DTIME}(\mathcal{E}^4)$, where $\mathcal{E}^4$ is the fourth level of the [Grzegorczyk hierarchy](http://en.wikipedia.org/wiki/Grzegorczyk_hierarchy) of primitive recursive functions. But that's still a pretty big class.)

> **Comments:**
> **username_0**: could you please provide a reference for this?  
> **username_1**: @Turbo: Which "this" do you want a reference for?  
> **username_0**: claim that every possible notion of randomness becomes trivial and reasoning about primitive recursive functions. Actually as many references to make it self contained is good.  
> **username_1**: @Turbo: For computable analogues of BPP being trivial I don't know a reference, but I essentially already gave the proof in the answer. (ML, Kurtz, Schnorr, etc. randomness are not analogous to BPP.) The thing about $\mathcal{E}^4$ follows directly from the definition, which is in the linked wikipedia article. Was there something more you wanted?  
> **username_0**: I am just wondering is there an analogue of sipser's theorem in arithmetic hierarchy?  
> **username_1**: @Turbo: As far as I know, there is not, precisely because there is no (known) interesting analogue of BPP in the arithmetic hierarchy...  
> **username_0**: one more very very trivial problem we know P=BPP implies NEXP is not in P/poly or perm does not have poly circuits. AFAIK perm needs superpoly circuits imply NEXP is not in P/poly. So why dont we just say P=BPP implies NEXP is not in P/poly?  
> **username_0**: I am talking theorem 4.7 here https://books.google.com/books?id=xPAnxps5PNgC&pg=PA97&lpg=PA97&dq=p+bpp+nexp+permanent&source=bl&ots=XQD4j5W5Ic&sig=BPK6EF7jToZJeqJTaBl7YiKM4NU&hl=en&sa=X&ved=0ahUKEwi2xvLIrYDKAhVBF2MKHaCNAHEQ6AEISzAI#v=onepage&q=p%20bpp%20nexp%20permanent&f=false I am confused why you need 1 and 2?  
> **username_1**: @Turbo: That's a separate question.  
> **username_0**: http://cs.stackexchange.com/questions/51274/query-on-consequences-of-p-bpp done  

---

