# Term for expected randomized given advice string?

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?

• Please distinguish average polynomial time and expected polynomial time. – Willard Zhan Feb 12 '17 at 12:33
• I have already clarified in last sentence. – T.... Feb 12 '17 at 12:36
• Also, please be clear which distributions are used over the inputs. Uniform distribution leads to exactly $\mathsf{E/poly}$ – Willard Zhan Feb 12 '17 at 13:25
• Are you talking about languages decidable using probabilistic (expected) polynomial time Turing machines with polynomial advice? – Ariel Feb 12 '17 at 17:58
• @WillardZhan clarified better. – T.... Feb 12 '17 at 19:37