Is there any difference between expected polynomial time and randomized polynomial time algorithm?

  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Oct 9 '16 at 12:43
  • 1
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Oct 9 '16 at 12:44

RP (randomized polynomial time) is a complexity class for algorithms that always run in polynomial time, while possibly make truly random choices, and always rejecting correctly while usually accepting correctly (i.e., with probability greater than $\frac{1}{2}$).

Expected polynomial time usually means that the complexity is polynomial time only in expectation, and the answer is always correct.

Suppose you have the following (silly) algorithm to check if the first element, in an array with length n, is the maximum:

  1. Scan the array, check if the first element is maximum.

  2. With probability $\left(\frac{1}{2}\right)^n$, uselessly scan the array an additional $\frac{2^n}{n}$ times, and recheck the result of step 1.

  3. Return the answer from 1 in any case.

This algorithm has expected polynomial time. The cost of the first step is $\Theta(n)$. The expected cost of the second step is $\Theta\left( \left(\frac{1}{2}\right)^n n \frac{2^n}{n}\right) = O(1)$. The cost of the third step is constant. Conversely, it is not in RP because the second step can run in time $\Theta\left( 2^n \right)$ for an unfortunate randomized outcome.

  • $\begingroup$ where did you get this example? It is expected poly because $\sum_{i=1}^\infty\frac1n<\log n$? $\endgroup$ – Bread Winner Oct 9 '16 at 7:06
  • $\begingroup$ @AJ. Added some details. $\endgroup$ – Ami Tavory Oct 9 '16 at 7:13
  • $\begingroup$ RP is not always correct, as the Wikipedia article to which you link explains. It is always correct on no-instances, but not on yes-instances (i.e. it is perfectly sound but not perfectly complete). So if the algorithm returns yes, you know that the answer is yes, whereas if the algorithms returns no, you might want to rerun the algorithm a bunch of times to be sure. The class of polynomial-time zero-error randomized algorithms is P, the more interesting class of expected polytime zero-error random algorithms is ZPP. $\endgroup$ – Lieuwe Vinkhuijzen Oct 9 '16 at 8:40
  • $\begingroup$ @LieuweVinkhuijzen You're right - many thanks! Will update. $\endgroup$ – Ami Tavory Oct 9 '16 at 8:42

Your Answer

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

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