Friday, December 18, 2009

What is an explicit Construction?

The Prob method (usually credited to Erdos) was once considered quite novel: You show something exists but you don't show how to construct it! An early example was lower bounds on the Ramsey Numbers: You can prove that there exists a 2-coloring of the edges of Kn with no monochromatic k-cliques where n=2k/2, and the proof does not give a way to construct the coloring! When Joel Spencer wrote his first book on The Probabilistic Method (appeared in 1974) this kind of argument was still considered novel. Now they are quite common. Such arguments were (and still are) called Nonconstructive. However, at the time, the term was not defined rigorously.

Of course, once you know that such a coloring exists, it is easy to find one by just looking at all possibly colorings. Hence this use of nonconstructive proofs would not be an issue for logicians.

Many of the early prob method arguments actually showed that most colorings have the property you want. Hence they would lead to randomized polynomial time algorithms. With this in mind, here is one possible definition that seems to cover what Erdos and company were thinking informally:

Definition: A coloring of an object X is constructive if it can be obtained in time polynomial in the size of X.

Is this a good definition? Now that we think P=BPP, or at least that BPP is a good notion of feasible, perhaps we should call randomized algorithms constructive. Moser and Tardos think so since there paper entitled A constructive proof of the General Lovasz Local Lemma has a randomized algorithm.

Here is a history of the prob method as applied to lower bounds on VDW numbers (see here for definitions and some of the proofs). Let W(k) be the least number such that, no matter how you 2-color {1,...,W(k)}, there will be a monochromatic arithmetic sequence of length k.
  1. W(k) &ge sqrt(k)2(k-1)/2 is an easy application of the Prob Method. The proof is so easy that I could not find it written down anywhere, so I wrote it down in the paper pointed to above.
  2. W(k) &ge sqrt(k)2(k-1)/2 can be proved constructively by the method of conditional expectations. This is also so easy that I could not find it written down anywhere. So I wrote it down myself in the paper pointed to above.
  3. Berlekamp showed that, if p is prime, then W(p) &ge p2p constructively. (I prove a slightly weaker result in the paper linked to above.) (Berlekamp's original paper can be found on my website of VDW papers: here.)
  4. Using the Local Lovasz Lemma one can show that W(p)&ge 2k/ek. This proof is nonconstructive and does not yield and almost-all result, so it cannot be turned into a randomized algorithm.
  5. Moser and Tardos (above link) (and later Beigel with a different proof) showed that the LLL can always be made to yield a prob algorithm. Hence they have a randomized algorithm to obtain a 2-coloring of {1,...,2k/ek} with no mono k-AP's. This is not a constructive algorithm in the way that Erdos or Spencer might accept, though it does yield a feasible algorithm.
  6. Chandrasekaran, Goyal, Haeupler in the paper Deterministic algorithms for the Lovasz Local Lemma have a deterministic version of the LLL with slightly worse bounds. From their paper one can obtain: W(k) &ge 2k/(1+&epsilon) via a poly algorithm.

8 comments:

  1. Somehow I'm hazy somewhat. So what would the definition of probabilistic constructive look like? Would it be some kind of epsilon-delta thing such as: For any any epsilon > 0 One can with probability 1-epsilon find the solution in polynomial time? Is there a standard way to say these things?

    ReplyDelete
  2. No, No, No! I don't care how much time it takes if I can demonstrates that something must exist by putting forth an algorithm to construct it then it, the proof is constructive.

    If I prove that something must exist then point out that because it exists an exhaustive search will find it, that is not constructive proof of it's existence, because a pre-requesite for the construction is the assumption that what you are looking for exists.

    So there is no need to further constrain the definition of constructive to avoid constructive proofs that are really non-constuctive proofs with an exhaustive search tacked onto the end, because it should be clear that the exhaustive search relies on the known existence of solution and thus is not constructing it. So all you do by adding the constraint is exclude some legitimately constructive proofs that just don't run in what you want to call "good time" from being categorized as constructive.

    ReplyDelete
  3. As a historical reminder, Claude Shannon's work in 1948-9 on channel capacity was famously nonconstructive ... and Joseph Doob's AMS review of Shannon's work was (perhaps in consequence?) famously snarky ...

    "(Shannon's) discussion is suggestive throughout, rather than mathematical, and it is not always clear that the author’s mathematical intentions are honorable."

    @article{Author = {Shannon, C. E.}, Journal = {Bell System Tech. J.}, Pages = {379--423, 623--656}, Title = {A mathematical theory of communication},Volume = {27}, Year = {1948},annote={see Doob's review: MR0026286}}

    ReplyDelete
  4. Markk: standard way to say it is
    There is a rand poly time algorithm
    that produces a correct coloring
    with prob \ge 3/4. AND you can test if its correct. So if its not you can run it again. This is equivalent to prob \ge 1/2^n (or somethign like that).

    Anon 2: You are using the LOGICIANS definition of Constructive.
    Perhaps combinatorists should use a diff term like Explicit.
    The distinction between a
    prob construction that just shows
    something exists and an explicit
    construction IS a real difference of interest.

    ReplyDelete
  5. Good point, Bill! The whole lower bounds stuff in computational complexity is also "sick" about finding a "constructive" or "explicit" or "specific" hard to compute function. And nobody in fact cares about what these terms actually mean. Why? Since there is no need to care. We all know what we want: to understand why some functions are easy and the others
    are hard. The same with "constructivity" in combinatorial proofs: if a good object exists, then it would be nice to try to see one constructed on 1-2 pages..

    What we actually want is not to construct ("explicitly" or however) some artificial "complex" objects -- we want to known what makes them "complex".

    Actually, I am also a bit confused by this big rumor about Robin Moser's result. It is a cute and nice idea, no doubts. It made some previous results simpler. But what it really says about *why* SAT problem is so difficult? LLL already said that one of the reasons is a big overlap between clauses. What one (as a mathematician, not an applier) gets from the knowledge that LLL for SAT can (sometimes) be turned to an efficient randomized algorithm?

    Possible meanings of "constructive object":

    (a) Can be constructed in principle.

    (b) Can be constructed in reasonable (polynomial) time.

    (c) Can be described on 1-2 pages.

    I think Paul Erdos (as well as most of people working on lower bounds for boolean functions) would accept neither (a) nor (b) as "constructive. This is why we are happy to see things like 1 page construction of almost Ramsey graphs by Frankl and Wilson, etc.

    ReplyDelete
  6. Bill, finally returning to the accustomed standard of this blog. Please keep up this standard.

    Nice post.

    ReplyDelete
  7. Could someone please post a link to the Beigel paper referenced in item 5.? thanks.

    ReplyDelete
  8. Calling such proofs 'probabilistic' has always bothered me because they're really counting arguments which make use of probability terminology to avoid some clunky multipliers which always cancel out in the end. They're all based on the idea that you count the amount of stuff that's removed, and in the end there's stuff left over, so they rely on the pigeon hole principle. One could say that any proof which doesn't rely on the pigeon hole principle is non-constructive, but using the pigeon hole principle across a linear number of elements doesn't have the same feel to it. What matters is the size of the set the principle is applied to.

    Since all constructive (in the logician sense) proofs implicitly give an algorithm for finding the solution, perhaps it's best to look at the asymptotic runtime of that algorithm. If it's polynomial then the construction is fairly direct, otherwise it's somewhat indirect.

    ReplyDelete