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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
10
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.)
answered Nov 26, 2013 at 23:08
-
$\begingroup$ could you please provide a reference for this? $\endgroup$– TurboCommented Dec 27, 2015 at 23:03
-
$\begingroup$ @Turbo: Which "this" do you want a reference for? $\endgroup$ Commented Dec 28, 2015 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$– TurboCommented Dec 28, 2015 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$ Commented Dec 28, 2015 at 21:14
-
$\begingroup$ I am just wondering is there an analogue of sipser's theorem in arithmetic hierarchy? $\endgroup$– TurboCommented Dec 29, 2015 at 0:37