On the ultimate complexity of factorials

AbstractIt has long been observed that certain factorization algorithms provide a way to write the product of many different integers succinctly. In this paper, we study the problem of representing the product of all integers from 1 to n (i.e. n!) by straight-line programs. Formally, we say that a sequence of integers an is ultimately f(n)-computable, if there exists a nonzero integer sequence mn such that for any n, anmn can be computed by a straight-line program (using only additions, subtractions and multiplications) of length at most f(n). Shub and Smale [12] showed that if n! is ultimately hard to compute, then the algebraic version of NP≠P is true. Assuming a widely believed number theory conjecture concerning smooth numbers in a short interval, a subexponential upper bound (exp(clognloglogn)) for the ultimate complexity of n! is proved in this paper, and a randomized subexponential algorithm constructing such a short straight-line program is presented as well