Are randomized algorithms constructive?

Question

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!

Answer 1

The probabilistic method is typically used to show that the probability of some random object having a certain property is non-zero, but doesn't exhibit any examples. It does guarantee that a "repeat-until-success" algorithm will eventually terminate, but does not give an upper bound on the runtime. So unless the probability of a property holding is substantial, an existence proof by the probabilistic method makes a very poor algorithm.

In point of fact, probabilistic algorithms aren't actually constructive existence proofs, so much as they are algorithms to produce constructive existence proofs. The output is an object of the sort which it was meant to prove the existence of; but the fact that it will eventually yield one ("there will exist an iteration in which it yields an example — except with probability zero...") is not enough to be constructive; it will only be satisfactory to someone who already accepts that non-zero-probability-without-construction suffices for existence. Conversely, if you do have a good bound on the run-time, then there's in principle no excuse not to run it in order to actually produce an example. A good probabilistic algorithm still isn't a constructive proof, but a good plan to obtain a constructive proof.

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.

Of course, one might adopt a philosophical position intermediate to constructivism and the classical approach to existence, and say that what one wants is not constructions per se but construction-schema which are allowed to fail with any probability less than one; that would make any probabilistic construction "schematic", if not completely constructive. Where one wishes to draw the line, to say that they find an existence proof "satisfactory", ultimately depends on how much intuition (in a non-philosophical sense) they wish to gain from proofs.

Answer 2

Uniform proof complexity is a field devoted (among else) to the study of constructive notions of proofs, and their relation to complexity classes. For each of the popular (uniform) circuit complexity classes, one can define a theory in which everything which is provable has a "backing" in an algorithm in this complexity class. Randomized algorithms are accommodated through versions of the pigeonhole principle (oddly enough).

Unfortunately I'm not an expert so I can't say much more, other than point you to the book by Cook and Nguyen (same Cook as in Cook's theorem) and to the work of Emil Jeřábek, especially his thesis on randomized computation.