A basic question about the connection between two notions. I am sure these are known notions in CS but I struggle with the basics:
First Definition:
A probabilistic algorithm $A(n)$ decides $L$ if for every $x \in L$, it holds that $\Pr(A(x) = 1) \geq 1 - \epsilon$, and for every $x \notin L, \Pr (A(x) = 0) \leq \delta$.
Second definition:
Given a language $L$ and a distribution $D$ on the instances of $L$, the algorithm $A$ decides $L$ with respect to $D$, if it holds that for every $x$ which is drawn from $D$, the above requirements hold ($\Pr(A(x) = 1)\geq ...$).
Clearly, the first notion is "stronger" in some sense: in the second definition, I may force the algorithm make as many mistakes as I want, by creating a different distribution on which he cannot handle.
My main question is the following:
If for a problem there exists an algorithm $A$ such that $A$ decides $L$ with respect to the uniform distribution, does it mean that $A$ decides $L$ for every input (with high probability)? I somewhat "feel" that uniform solving for a uniform distribution is harder, does this feeling correct?


1 Answer 1


The first notion (probabilistic algorithms who are correct with high probability for all inputs) is indeed stronger. Distributional complexity relates to randomized (worst case) complexity via Yao's principle, which states that the worst case expected running time of any randomized algorithm, is no better than the expected running time of the best deterministic algorithm for any input distribution.

You can find an exact formulation in this cstheory question, where both the Las Vegas (the randomized algorithm should always output the correct answer) and the Monte Carlo case (similar to your formulation) are mentioned.

As for your question, it is not true that an algorithm which outputs the correct answer with high probability when the input is drawn according to the uniform distribution, returns the correct answer with high probability for all inputs. Consider an algorithm which answers correctly for all inputs not of the form $0^n$. For an input drawn from the uniform distribution, the probability of getting a correct answer is $1-2^{-n}$, however for inputs of the form $0^n$ you never get the correct answer.

  • $\begingroup$ does 1−2−n read like this: One minus two squared minus n? $\endgroup$
    – undefined
    Commented Jul 6, 2018 at 6:41
  • 1
    $\begingroup$ $1-\frac{1}{2^n}$ $\endgroup$
    – Ariel
    Commented Jul 6, 2018 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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