3
$\begingroup$

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.

  1. Concerning Goldreich09 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 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.

Improve this question
$\endgroup$
3
  • $\begingroup$ In (1) I think you mean BPP rather than PP. $\endgroup$
    – Huck Bennett
    Sep 23, 2011 at 19:38
  • 1
    $\begingroup$ @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). $\endgroup$
    – Paolo Parisen T.
    Sep 26, 2011 at 10:55
  • 1
    $\begingroup$ Related: cstheory.stackexchange.com/questions/2515/… $\endgroup$
    – Tsuyoshi Ito
    Sep 27, 2011 at 14:03

1 Answer 1

Reset to default
6
$\begingroup$

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

As for your question 1, your class is 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 halts before executing step 1 more than t times, and that the probability of error is at most 1/2−1/2t < 1/2. The expected number of times step 1 is executed is 2(1−1/2t) < 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, 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 by Karolina Sołtys.)

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Paolo Parisen T.
    Oct 1, 2011 at 9:19
  • $\begingroup$ (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. $\endgroup$
    – Paolo Parisen T.
    Oct 1, 2011 at 9:25
  • $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Oct 1, 2011 at 10:24
  • $\begingroup$ 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 $\endgroup$
    – Paolo Parisen T.
    Oct 2, 2011 at 21:31
  • $\begingroup$ @Paolo: I found it out exactly as you did. $\endgroup$
    – Tsuyoshi Ito
    Oct 2, 2011 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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