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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.