The Computer Science Colloquium

Aviezri S. Fraenkel
(Weizmann Institute of Science)

"Complexity of a Sequences Membership Question"

    The question whether an m-tuple (x₁, ... , x_m) Z^m_≥0 is in (a¹, ... , a^m), where the aⁱ 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 a_i. Specifically, we consider the complementary sequences a_n = mex{a_i, b_i : 0 ≤ i < n}, b_n = a_n + n/k (sequences A102528/9 in Sloane’s encyclopedia for k = 2). Using Fekete’s Lemma we show that the polynomially computable sequences s_n = nα, t_n = nβ where α = (√17 + 3)/4, β = α + 1/2 are very good approximations, namely, s_n−1 ≤ a_n ≤ s_n, t_n−1 ≤ b_n ≤ t_n for all n ≥ 1 (k = 2). We conjecture that the percentage of n for which a_n = s_n−1 is about 73%, a_n = s_n, 19%, a_n = s_n −2, 8%. Similar results for b_n, t_n. 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 (a¹, ..., a^m) are the second player winning positions.
      Joint work with Udi Hadad.

The Colloquium is supported by generous contributions from the Bloomberg, Information Builders, Inc., and Netlogic, Inc.