I have occasionally seen some comments on this blog as to how one can never know too much math. To support this statement, here is an example of a beautiful application of math to proving lower bounds.
Given n numbers, the k-equal problem must decide whether there are k numbers which are equal. When k=2 this is the classic element distinctness problem, and when k>n/2 this is a classic exercise. What is the complexity of the problem for general k? In 1992 Bjorner, Lovasz and Yao proved a lower bound of at least a constant times n*log (2n /k). Here is an executive summary (summarized from Bjorner and Stanley's paper, A Combinatorial Miscellany).
From computational complexity to algebraic topology: Each equation x(i1)=x(i2)=...=x(ik) defines a (n-k+1) dimensional subspace. Removing all these subspaces defines a space M, and it can be proved that the complexity of the k-equal problem is at least logarithmic in b(M), the sum of the Betti numbers of M.
From algebraic topology to combinatorics: Let P(n,k) denote the partial order whose elements are the partitions of {1,2,...,n} whose parts all have size either equal to 1 greater than or equal to k, ordered by the "merging" partial order. A combinatorial formula of Goresky and MacPherson implies that b(M) is at least the absolute value of m(n,k), the value of the Mobius function of the set {1,2,...,n}.
Definition: Given a partial order with a bottom and a top element, the Mobius function is defined recursively by: m(bottom element)=1 and m(x) is the sum, over every y less than x, of -m(y).
Enumerative combinatorics: As it turns out, m(n,k+1) can be expressed in terms of the complex roots of the polynomial 1+x+x^2/2!+...+x^k/k! From this, for k fixed and n variable, one can prove that there is a subsequence of m(n,k) which grows quickly enough to prove the stated lower bound.
Comments page (Usual comments link does not work properly, use this instead.)
Claire
No comments:
Post a Comment