Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu
Lara Pudwell, Rutgers University, lpudwell {at} math [dot] rutgers [dot] edu
Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Polynomial Approximation of Computationally-Hard Sequences

Speaker: Aviezri Fraenkel, Weizmann Institute, Israel

Joint Talk with Mathematics Colloquium

Date: Thursday, December 6, 2007 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


The question whether an m-tuple (x1,...,xm) in Z≥ 0m is in (a1,...,am), where the ai are given integer sequences, can sometimes be decided efficiently (in polynomial time). More often, the answer is unknown, the best known algorithms being exponential. We present a polynomial approximate algorithm for deciding this question for some sequences ai. Specifically, we consider the complementary sequences an=mex{ai, bi : 0 ≤ i < n}, b=an + |_ n/k _| (sequences A102528/9 in Sloane's encyclopedia for k=2). Using Fekete's Lemma we show that the polynomially computable sequences sn=|_n α_|, tn=|_n β_| where α = (√(17)+3)/4, β=α+1/2 are very good approximations, namely, sn-1 ≤ an ≤ sn, tn-1 ≤ bn ≤ tn for all n ≥ 1 (k=2). We conjecture that the percentage of n for which an=sn-1 is about 73%, an=sn, 19%, an=sn-2, 8%. Similar results for bn, tn. Analogous results for every fixed k>1. Existence of a limiting distribution, with one of the percentages dominant, would lead to first probabilistic algorithms for determining the winning positions of certain impartial games, where the (a1, ..., am) are the second player winning positions.

Joint work with Udi Hadad.