# Are randomized algorithms constructive?

From , the proofs by the probabilistic method are often said to be non-constructive.

However, a proof by probabilistic method indeed designs a randomized algorithm and uses it for proving existence. Quoted from p103 of Randomized Algorithms By Rajeev Motwani, Prabhakar Raghavan:

We could view the proof by the probabilistic method as a randomized algorithm. This would then require a further analysis bounding the probability that the algorithm fails to find a good partition on a given execution. The main difference between a thought experiment in the probabilistic method and a randomized algorithm is the end that each yields. When we use the probabilistic method, we are only concerned with showing that a combinatorial object exists; thus, we are content with showing that a favorable event occurs with non-zero probability. With a randomized algorithm, on the other hand, efficiency is an important consideration - we cannot tolerate a miniscule success probability.

So I wonder if randomized algorithms are viewed as not constructive, although they do output a solution at the end of each run, which may or may not be an ideal solution.

How is an algorithm or proof being "constructive" defined?

Thanks!

• Since there isn't any agreed-on definition of "constructive" as a technical term, and there isn't any central authority to give the definition of "constructive", and since different people will have different definitions (possibly depending on which subfield of computer science or mathematics they come from), I really don't think there can be a definitive answer to this question. – Peter Shor Oct 24 '12 at 12:33
• I just ask about its most common meaning for proofs and algorithms. I think randomized algorithms are constructive, but proving by the probabilistic method isn't although it has a randomized algorithm inside, and therefore confused. – Tim Oct 24 '12 at 12:39
• According to wikipedia, which doesn't mention time complexity, almost all proofs using the probabilistic algorithm would be constructive, since they give (very inefficient) algorithms. It depends on context. – Peter Shor Oct 24 '12 at 12:42
• @PeterShor: isn't "constructive" approximately as well-defined a term as "logic" itself is? Without clarification, I would have assumed that a constructive result was one which involved ZF set theory and used constructive logic. – Niel de Beaudrap Oct 24 '12 at 13:02
• I never heard "constructive" used to describe algorithms, only proofs. – Raphael Oct 25 '12 at 8:21

Note that this idea, that a randomized algorithm is a proof strategy (as opposed to a proof in itself) to demonstrate an existential quantification, is not unlike the idea that induction is a good proof strategy to show a universal quantification (over the natural numbers). This analogy may seem compelling, as induction is essentially the heart of recursion as a computational technique. (For any positive integer $n$, if you want to decide whether $n^2$ is a sum of the consecutive odd numbers preceding $2n+1$, you can reduce this to investigating whether $(n-1)^2$ is a sum of the consecutive odd numbers preceding $2n-1$, and so forth.) Induction is essentially an algorithmic proof-strategy which we have elevated to a theorem, allowing us to have the knowledge without explicitly computing it each time. However, induction is accepted constructively because it is already an axiom(-scheme) of Peano arithmetic, and one which is independent of the other axioms. By contrast, there is no rule of inference or axiom which allows the probabilistic method to prove existence constructively, or to constructively prove that probabilistic algorithms produce existence proofs, or anything along these lines. You simply cannot prove that there are examples of a class of object from the fact that there is a probabilistic algorithm to construct it, unless you already accept that proposition, either as an axiom, or from other premises.