Nonconvergence, undecidability, and intractability in asymptotic problems

Abstract

Results delimiting the logical and effective content of asymptotic combinatorics are presented. For the class of binary relations with an underlying linear order, and the class of binary functions, there are properties, given by first-order sentences, without asymptotic probabilities; every first-order asymptotic problem (i.e., set of first-order sentences with asymptotic probabilities bounded by a given rational number between zero and one) for these two classes is undecidable. For the class of pairs of unary functions or permutations, there are monadic second-order properties without asymptotic probabilities; every monadic second-order asymptotic problem for this class is undecidable. No first-order asymptotic problem for the class of unary functions is elementary recursive.