Theoretical Computer Science

Arithmetic Analogues of P versus BPP

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.


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 of primitive recursive functions. But that's still a pretty big class.)

Comments (5)

  • +0 – could you please provide a reference for this? — Dec 27, 2015 at 23:03  
  • +0 – @Turbo: Which "this" do you want a reference for? — Dec 28, 2015 at 20:56  
  • +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. — Dec 28, 2015 at 20:59  
  • +0 – @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? — Dec 28, 2015 at 21:14  
  • +0 – I am just wondering is there an analogue of sipser's theorem in arithmetic hierarchy? — Dec 29, 2015 at 00:37  

External Links

External links referenced by this document: