Content area
Abstract
In this dissertation, logical methods are used to prove lower bounds for the complexity of computing certain number-theoretic and algebraic functions. The computations are assumed to be relative to a fixed basis of given operations, and lower bounds are proved for a time complexity which measures the number of calls to the primitives. In one case, as a corollary to a lower bound, the optimality of a known algorithm is established.
The lower bounds are obtained through the construction of certain parametric, asymmetric embeddings. In Chapter 2, an embedding is defined on an algebra of (rational) integers. Embeddings which are similar in spirit to this one are constructed in Chapter 3 on algebras of each of the imaginary norm-Euclidean quadratic integer rings, including the rings of Gaussian and Eisenstein integers. A key issue in the definition of such embeddings involves the interplay of the metric and multiplicative structure of the underlying algebra.
The lower bounds are proved for recursive programs, where parameters are assumed to be passed by value. In Chapter 4, it is shown how the same lower bounds hold for a version of call-by-name PCF, a simply-typed λ-calculus with recursion operators at each type.
In Chapter 5, results that are related to those of the dissertation are discussed. In addition, relevant known algorithms are presented. A unifying feature of this work is that algorithms for computing many of the functions for which lower bounds are obtained are similar to the so-called "binary algorithm" of Stein [Ste67], and, like Stein's algorithm, rely only on piecewise-linear primitive operations.