i have some question concerning the class PP and PPT machines.
- 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.
- 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.