Problems which run in deterministic polynomial time given polynomial sized advice are in class P/poly. Problems which run in probabilistic polynomial time given polynomial sized advice are still in class P/poly. What about problems which have an expected randomized polynomial time given polynomial sized advice under uniform distribution of inputs where expected here signifies average in the sense that a very small portion of inputs are allowed to run in exponential time using the algorithm?
Term for expected randomized given advice string?
complexity theory;randomness