Analog of PP for computability rather than complexity?

Question

The complexity class PP can be defined in many ways, one of which involves randomness - a language $L$ is in PP if there is a polynomial-time, randomized TM $M$ such that $w \in L$ if and only if the probability that $M$ accepts $w$ is greater than 1/2.

I'm curious whether there is a name for the complexity class that can be obtained by relaxing the definition so that the randomized TM doesn't necessarily have to run in polynomial time. Specifically, consider the class of languages $L$ such that there is a TM $M$ where $w \in L$ if and only if the probability that $M$ accepts $w$ is greater than 1/2. There is no requirement that this TM halt on all inputs.

Where does this class of problems lie? This class contains RE because any recognizer accepts a string $w \in L$ with probability 1 and accepts any string $w \notin L$ with probability 0. I doubt that it's equal to RE, though, since I can't see how you could convert this "majority recognizer" for $L$ into an actual recognizer for $L$. I tried placing it somewhere in the arithmetical hierarchy, but I don't see how to encode the concept "more than half of the computation branches accept" into some first-order formula involving alternating quantifiers.

Does this class of problems already exist and have a name? If so, what is it?

Thanks!

Answer 1

"this class of problems lie"s in RE, so its name is "RE".

$$\begin{align*}\operatorname{Prob}(M \text{ accepts}) &= \operatorname{Prob}\big((\exists n)(M \text{ accepts after exactly $n$ steps})\big)\\ &=\sum_n \operatorname{Prob}(M \text{ accepts after exactly $n$ steps})\\ &=\lim_N \sum_{n\leq N} \operatorname{Prob}(M \text{ accepts after exactly $n$ steps})\\ &=\lim_N \;\operatorname{Prob}(M \text{ accepts in at most $N$ steps}) \\ &= \lim_n \; \operatorname{Prob}(M \text{ accepts in at most $n$ steps})\,. \end{align*}$$

For all $m$ and $n$ with $m\leq n$, and for all randomness strings $r$, $M$ accepts in at most $m$ steps if and only if it accepts in exactly some $t\leq m$ steps. But then $t\leq n$ so this can only occur if $M$ accepts in at most $n$ steps with randomness string $r$.

For all $m$ and $n$, with $m\leq n$, the probability that $M$ accepts in at most $m$ steps does not exceed the probability that it accepts in at most $n$ steps.

$$\begin{align*} &\tfrac12 < \operatorname{Prob}(M \text{ accepts}) \\ &\iff \tfrac12 < \lim_n \; \operatorname{Prob}(M \text{ accepts in at most $n$ steps})\\ &\iff (\exists n)\left(\tfrac12 < \operatorname{Prob}(M \text{ accepts in at most $n$ steps})\right)\,. \end{align*}$$

Therefore, a machine that loops over the positive integers $n$ and accepts if and only if $\tfrac12 < \operatorname{Prob}(M \text{ accepts in at most $n$ steps})$ will accept exactly the inputs that $M$ has a probability greater than $\tfrac12$ of accepting.

Answer 2

The ideas in this answer come directly from Ricky Demer. I wanted to write a more long-form answer that fills in a few of the details and justifies why this new complexity class is equal to RE.

First, let's introduce some notation. Let's call the complexity class described in this problem PRE for "probabilistic RE." We'll say that a language $L$ is in PRE if and only if there is a randomized TM $M$ such that

$$w \in L \leftrightarrow Pr[M \mbox{ accepts } w] \gt \frac{1}{2}$$

The question now is how RE and PRE relate to one another. The goal will be to prove this theorem:

Theorem: PRE = RE

To prove this, we'll show that each set is a subset of the other. One direction here happens to be relatively easy:

Theorem: RE $\subseteq$ PRE.

Proof: Consider an arbitrary $L \in$ RE. Since $L$ is in RE, there must be a TM $M$ that recognizes $L$. Specifically, for any string $w$, if $w \in L$, then $M$ accepts $w$, and if $w \notin L$, then $M$ does not accept $w$. Now, we can construct a randomized TM $M'$ that's basically the same as $M$; it doesn't actually use any randomness. As a result, if $w \in L$, then $Pr[M \mbox{ accepts } w] = 1$ and if $w \notin L$, then $Pr[M \mbox{ accepts } w] = 0$. Consequently, $L \in $ PRE.

The other direction of implication is the harder one. We're going to show that if you start with an arbitrary PRE language, you can prove that it's also an RE language. Equivalently, we'll show how to start with a randomized TM $M$ meeting the criteria of PRE and then show how to construct a recognizer for it.

Let $$M$$ be any randomized TM. Our goal will be to prove the following key lemma:

Lemma: $Pr[M \mbox{ accepts } w] \gt \frac{1}{2}$ if and only if there is some $n \in \mathbb{N}$ where $Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}] \gt \frac{1}{2}$

For now, let's assume the lemma is true. This gives rise to an elegant way to build a recognizer for any PRE language. Counting up from $n=1$, exhaustively list all computation paths through $M$ whose length is at most $n$ and explicitly compute the probability that $M$ accepts within $n$ steps. If at any point we find that this probability is greater than 1/2, by the lemma we know that the overall probability that $M$ accepts is greater than 1/2, so the input string $w$ must belong to $L$.

On the other hand, suppose that we never find an $n$ for which the acceptance probability within $n$ steps is greater than 1/2. That means that the acceptance probability for each computation length is at most 1/2. Since

$$Pr[M \mbox{ accepts } w] = \lim_{n \rightarrow \infty} Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}]$$

we would conclude that $Pr[M \mbox{ accepts } w] \le \frac{1}{2}$, meaning that $w \notin L$. In other words, the TM that just brute-force checks the acceptance probability for each computation length would be a recognizer for $L$, and so we'd see that PRE $\subseteq$ RE.

Everything hinges on this key lemma, so let's see how we might go about proving it. One direction is easier. Let's argue that if $Pr[M \mbox{ accepts } w] \gt \frac{1}{2}$, then there must be some $n$ such that $Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{steps}] \gt 1/2$. As mentioned above, we know that

$$Pr[M \mbox{ accepts } w] = \lim_{n \rightarrow \infty} Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}]$$

Therefore, if we assume that $Pr[M \mbox{ accepts } w] \gt \frac{1}{2}$, we know that

$$\lim_{n \rightarrow \infty} Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}] \gt \frac{1}{2}$$

We can use the formal definition of a limit to conclude from this that there must be at least one $n \in \mathbb{N}$ such that $Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}] \gt \frac{1}{2}$.

For the other direction, we need this additional result: if $m \le n$, then

$$Pr[M \mbox{ accepts } w \mbox{ within } m \mbox{ steps}] \le Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}]$$

Intuitively, this says that the acceptance probability as a function of the length of the computations considered is nondecreasing. Why is this? If you run a computation for $m$ steps and then continue to run it for one more step, all of the branches that were already accepting are still accepting. If none of the new branches exposed by running the TM for one more step are accepting, then the new acceptance probability is the same as the old acceptance probability. If any of the new branches exposed are accepting, the acceptance probability goes up.

Given this, we can say that if the acceptance probability after some number of steps $n$ ever exceeds $\frac{1}{2}$, then the acceptance probability for all larger numbers of steps also exceeds $\frac{1}{2}$, so the limit of the acceptance probability is also greater than $\frac{1}{2}$.

To summarize:

• RE $\subseteq$ PRE since any recognizer fulfills the conditions of a randomized TM for a PRE language.
• If we have a randomized TM meeting the requirements for a PRE language, then that TM accepts a string with probability greater than one half if and only if after some finite number of steps the acceptance probability exceeds one half. We can then build a recognizer for the language by simulating branches of the randomized TM and checking, at each point, whether the acceptance probability is at least one half.

Hope this helps!