Room 139,
Computer Science and Applied
Mathematics
Weizmann Institute of Science
aviezri.fraenkel@weizmann.ac.il
Abstract: The question whether an m-tuple
(x1, . . . , xm) 2 Zm _0 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. Specifi-
cally, we consider
the complementary sequences an = mex{ai, bi : 0 _ i < n}, bn = an + bn/kc (sequences
A102528/9 in Sloane’s encyclopedia for k = 2). Using Fekete’s
Lemma we show that the polynomially computable sequences
sn = bn_c, tn = bn_c where _ = (p17 + 3)/4,
_ = _ + ˝ 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.