The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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.