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.)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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