<p>(This is a more detailed version of my comment on the question.)</p>

<p>As for your question 1, your class is <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#r" rel="nofollow noreferrer">R</a>, the class of decidable problems.  Expected polynomial time is not a useful resource restriction when you allow unbounded error.</p>

<p>To prove that your class contains R, consider a language <i>L</i>∈R.  Let <i>M</i> be a Turing machine for <i>L</i> which halts on every input.  Then we construct a probabilistic Turing machine <i>M</i>′ which runs in expected polynomial time as follows:</p>

<ol>
<li>Simulate one step of <i>M</i>.  If <i>M</i> accepts, then accept.  If <i>M</i> rejects, then reject.  If <i>M</i> has not halted, continue.</li>
<li>Halt and accept with probability 1/4, halt and reject with probability 1/4, and go to step 1 with probability 1/2.</li>
</ol>

<p>It should be easy to see that if <i>M</i> halts after <i>t</i> steps, then <i>M</i>′ <a href="http://en.wikipedia.org/wiki/Almost_surely#.22Almost_sure.22_versus_.22sure.22" rel="nofollow noreferrer">surely</a> halts before executing step 1 more than <i>t</i> times, and that the probability of error is at most 1/2−1/2<sup><i>t</i></sup> &lt; 1/2.  The expected number of times step 1 is executed is 2(1−1/2<sup><i>t</i></sup>) &lt; 2, and therefore <i>M</i>′ runs in expected constant time.</p>

<p>To prove that your class is contained in R, first note that finite expected running time implies that the probabilistic Turing machine halts <a href="http://en.wikipedia.org/wiki/Almost_surely#.22Almost_sure.22_versus_.22sure.22" rel="nofollow noreferrer">with probability 1</a>, and therefore your requirement implies that the machine halts with the correct answer with probability greater than 1/2.  Simulate the probabilistic Turing machine, accumulating the probability of acceptance <i>p</i> and the probability of rejection <i>q</i>.  Because the machine gives the correct answer with probability greater than 1/2, either <i>p</i> or <i>q</i> exceeds 1/2 eventually, and at this point we can stop the simulation and give the correct answer.  (For more details, see <a href="https://cstheory.stackexchange.com/questions/2515/can-a-probabilistic-turing-machine-solve-the-halting-problem/2519#2519">this answer</a> by Karolina Sołtys.)</p>

CC BY-SA 3.0
2011-10-01T09:19:15.317Z
could you explain me better why the probability error has to be $1/2−1/2^t < 1/2$? for example. Suppose M stops after 10 steps. the simulator M' then could do the following steps. 1) it makes the 1st step of simiulation 2) halts rejecting at second step.
So, with 1/4 of probability could take the wrong answer and this does not depend on how many steps M takes to compute.
Paolo Parisen T.
CC BY-SA 3.0
2011-10-01T09:25:36.367Z
(continuing the previous comment) well, obviously the number of steps of M' is bounded by the number of steps of M.
By the way, your proof seems interesting.
Paolo Parisen T.
CC BY-SA 3.0
2011-10-01T10:24:02.510Z
@Paolo: I do not know what your comment is asking.  As you correctly noticed, this algorithm produces a wrong output with probability at least 1/4 if t≥2, and that is why the error probability I claim is 1/2−1/2^t ≥ 1/4 for every t≥2.  To prove this error probability, use the formula for geometric series.
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-02T21:31:45.810Z
forgive me, but i was thinking about the following. suppose that the wrong answer is "no". Then i have $1/4$ of possibility to say no at the first round. $1/4 \times 1/2$ to say no at second round... and so on.
So, for my point of view it seems that the error bound is $1/4\times \sum_{i=0}^{t}1/2^i$.
So, $1/4 + 1/4\times \sum_{i=1}^{t}1/2^i$ that is bounded by $1/4 + 1/4\times 1 = 1/2$
From this point of view, the error bound seems to me more clear.
So, what i was saying was concerning how did you find out that expression?
thank in advance
Paolo Parisen T.
CC BY-SA 3.0
2011-10-02T23:23:04.257Z
@Paolo: I found it out exactly as you did.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-29T21:28:00.240Z
2013-04-21T16:44:33.140Z
2017-04-13T12:32:28.053Z
Tsuyoshi Ito
<p>i have some question concerning the class PP and PPT machines.</p>
<ol>
<li>PP is defined as the class of problems <span class="math-container">$L$</span> for wich exist a probabilistic turing machine running in polytime with error probability &lt; 1/2.</li>
</ol>
<p>I would like to know if there exists a complexity class that says in the following way (or something similar). &quot;The class of problem <span class="math-container">$L$</span> for wich exist a probabilistic turing machine running in expected(or avarage) polytime with error probability &lt; 1/2.&quot;
I took a look at complexity zoo, papadimitriou and arora-barak books but nothing seems concerning this aspect.</p>
<ol start="2">
<li>Concerning <a href="https://doi.org/10.1007/s00145-009-9050-5" rel="nofollow noreferrer">Goldreich09</a> it seems that Expected Probabilistic Polinomial Time (EPPT) is defined regarding a strategy. Are there alternatives definition of EPPT not related to adversaries and interactive machines or EPPT is strictly linked with strategies and adversaries?</li>
</ol>
<p>By question arises for the following reason. In <a href="http://www.wisdom.weizmann.ac.il/%7Efeige/thesis.ps" rel="nofollow noreferrer">Feige phd thesis</a> there is written (page 10):</p>
<blockquote>
<p>A probabilistic Turing Machine is expected polynomial time, if for any input, its expected running time (over random flips) is polynomial.</p>
</blockquote>
<p>This definition don't say anything about adversaries.</p>
<p>the first question then follows. can we create a complexity set of problem by using Probabilistic TM running in EPPT?</p>
<p>Thank in advance.</p>

CC BY-SA 3.0
2011-09-23T19:38:05.090Z
In (1) I think you mean BPP rather than PP.
Huck Bennett
CC BY-SA 3.0
2011-09-26T10:55:28.903Z
@Huck Bennet. No, i mean PP. BPP has a stronger constrain on the probability error. e < 1/2 - c (so, a constant away from 1/2).
Paolo Parisen T.
CC BY-SA 3.0
2011-09-27T14:03:21.740Z
Related: http://cstheory.stackexchange.com/questions/2515/can-a-probabilistic-turing-machine-solve-the-halting-problem
Tsuyoshi Ito
<cc.complexity-theory><complexity-classes><pr.probability><average-case-complexity>
Avarage classes for PP (probabilistic polynomial time) and PPT machines running in expected polytime
Paolo Parisen T.
# Avarage classes for PP (probabilistic polynomial time) and PPT machines running in expected polytime

(Asked by: username_0 on 2011-09-23)

i have some question concerning the class PP and PPT machines.

1. PP is defined as the class of problems $L$ for wich exist a probabilistic turing machine running in polytime with error probability < 1/2.

I would like to know if there exists a complexity class that says in the following way (or something similar). "The class of problem $L$ for wich exist a probabilistic turing machine running in expected(or avarage) polytime with error probability < 1/2."
I took a look at complexity zoo, papadimitriou and arora-barak books but nothing seems concerning this aspect.

2. Concerning [Goldreich09](https://doi.org/10.1007/s00145-009-9050-5) it seems that Expected Probabilistic Polinomial Time (EPPT) is defined regarding a strategy. Are there alternatives definition of EPPT not related to adversaries and interactive machines or EPPT is strictly linked with strategies and adversaries?

By question arises for the following reason. In [Feige phd thesis](http://www.wisdom.weizmann.ac.il/%7Efeige/thesis.ps) there is written (page 10):

> A probabilistic Turing Machine is expected polynomial time, if for any input, its expected running time (over random flips) is polynomial.

This definition don't say anything about adversaries.

the first question then follows. can we create a complexity set of problem by using Probabilistic TM running in EPPT?

Thank in advance.

**Tags:** cc.complexity-theory, complexity-classes, pr.probability, average-case-complexity
> **Comments:**
> **username_1**: In (1) I think you mean BPP rather than PP.  
> **username_0**: @Huck Bennet. No, i mean PP. BPP has a stronger constrain on the probability error. e < 1/2 - c (so, a constant away from 1/2).  
> **username_2**: Related: http://cstheory.stackexchange.com/questions/2515/can-a-probabilistic-turing-machine-solve-the-halting-problem  

---

## 1 answers

### Answer by username_2 on 2011-09-29. Score: 6

(This is a more detailed version of my comment on the question.)

As for your question 1, your class is [R](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#r), the class of decidable problems. Expected polynomial time is not a useful resource restriction when you allow unbounded error.

To prove that your class contains R, consider a language *L*∈R. Let *M* be a Turing machine for *L* which halts on every input. Then we construct a probabilistic Turing machine *M*′ which runs in expected polynomial time as follows:

1. Simulate one step of *M*. If *M* accepts, then accept. If *M* rejects, then reject. If *M* has not halted, continue.
2. Halt and accept with probability 1/4, halt and reject with probability 1/4, and go to step 1 with probability 1/2.

It should be easy to see that if *M* halts after *t* steps, then *M*′ [surely](http://en.wikipedia.org/wiki/Almost_surely#.22Almost_sure.22_versus_.22sure.22) halts before executing step 1 more than *t* times, and that the probability of error is at most 1/2−1/2*t* < 1/2. The expected number of times step 1 is executed is 2(1−1/2*t*) < 2, and therefore *M*′ runs in expected constant time.

To prove that your class is contained in R, first note that finite expected running time implies that the probabilistic Turing machine halts [with probability 1](http://en.wikipedia.org/wiki/Almost_surely#.22Almost_sure.22_versus_.22sure.22), and therefore your requirement implies that the machine halts with the correct answer with probability greater than 1/2. Simulate the probabilistic Turing machine, accumulating the probability of acceptance *p* and the probability of rejection *q*. Because the machine gives the correct answer with probability greater than 1/2, either *p* or *q* exceeds 1/2 eventually, and at this point we can stop the simulation and give the correct answer. (For more details, see [this answer](https://cstheory.stackexchange.com/questions/2515/can-a-probabilistic-turing-machine-solve-the-halting-problem/2519#2519) by Karolina Sołtys.)

> **Comments:**
> **username_0**: could you explain me better why the probability error has to be $1/2−1/2^t < 1/2$? for example. Suppose M stops after 10 steps. the simulator M' then could do the following steps. 1) it makes the 1st step of simiulation 2) halts rejecting at second step. So, with 1/4 of probability could take the wrong answer and this does not depend on how many steps M takes to compute.  
> **username_0**: (continuing the previous comment) well, obviously the number of steps of M' is bounded by the number of steps of M. By the way, your proof seems interesting.  
> **username_2**: @Paolo: I do not know what your comment is asking.  As you correctly noticed, this algorithm produces a wrong output with probability at least 1/4 if t≥2, and that is why the error probability I claim is 1/2−1/2^t ≥ 1/4 for every t≥2.  To prove this error probability, use the formula for geometric series.  
> **username_0**: forgive me, but i was thinking about the following. suppose that the wrong answer is "no". Then i have $1/4$ of possibility to say no at the first round. $1/4 \times 1/2$ to say no at second round... and so on. So, for my point of view it seems that the error bound is $1/4\times \sum_{i=0}^{t}1/2^i$. So, $1/4 + 1/4\times \sum_{i=1}^{t}1/2^i$ that is bounded by $1/4 + 1/4\times 1 = 1/2$ From this point of view, the error bound seems to me more clear. So, what i was saying was concerning how did you find out that expression? thank in advance  
> **username_2**: @Paolo: I found it out exactly as you did.  

---

