6
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ As described, the class is strictly larger than RE. It contains the language consisting of Turing Machines that halt. Here is the recognizer: simulate the input; if it ever halts, then accept; otherwise, do nothing. This accepts any string in the language with probability $1$. $\endgroup$ – usul Dec 10 '14 at 4:17
  • $\begingroup$ @usul That problem is also in RE for the same reason, though. $\endgroup$ – templatetypedef Dec 10 '14 at 9:29
  • $\begingroup$ You just defined it, so now it exists. Hint: given a randomized TM, construct a usual TM that (semi-)solves the same problem. $\endgroup$ – Raphael Dec 10 '14 at 11:26
  • $\begingroup$ @templatetypedef, D'oh, I was thinking of recursive. $\endgroup$ – usul Dec 10 '14 at 15:09
  • $\begingroup$ @Raphael The key insight came from Ricky Demer. I didn't realize that if you did a layer-by-layer search of the randomized TM branches, any time you hit a layer with above 50% accept probability you could conclude that the whole computation has over a 50% accept probability. $\endgroup$ – templatetypedef Dec 17 '14 at 1:25
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why is the probability that M accepts in at most n steps nondecreasing? Couldn't you build a TM that rejects with higher and higher probability as the machine runs longer and longer? $\endgroup$ – templatetypedef Dec 10 '14 at 0:07
  • $\begingroup$ @templatetypedef because it's the cumulative probability - the chance that the machine accepts at this step, plus any step before, so even if the probability decreases as $n$ increases, you're adding up the chance that it accepts on step 1 plus not on step on but step 2, plus not by 2 but on 3 etc. $\endgroup$ – Luke Mathieson Dec 10 '14 at 0:11
  • $\begingroup$ @templatetypedef : $\:$ One could "build a TM that rejects with higher and higher probability as $\hspace{.75 in}$ the machine runs longer and longer", but that says very little about its acceptance probability. $\hspace{.75 in}$ $\endgroup$ – user12859 Dec 10 '14 at 0:24
  • 1
    $\begingroup$ Can you state a bit more explicitly what your argument is here? A potential bug I'm worried about is if it relies on the $n$ in the last line being computable, which might not be the case. Or an assumption that $Pr[ M$ halts $] > \frac{1}{2}$ on all inputs. $\endgroup$ – usul Dec 10 '14 at 4:14
  • $\begingroup$ I find this completely impenetrable. Please explain what you're doing instead of just listing formulas. $\endgroup$ – David Richerby Dec 10 '14 at 8:42
5
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Thanks -- this is a much clearer answer and deserves more votes. $\endgroup$ – David Richerby Dec 13 '14 at 12:57

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.