Arithmetic Circuits in Mathematical Logic
Lead Research Organisation:
University of Manchester
Department Name: Computer Science
Abstract
One of the central concerns of Theoretical Computer Science is to understand the expressiveness of different formalisms for specifying computational processes. What computations can be specified in one formalism that cannot be specified in some other? What is the cost of translating from a specification in one formalism to a specification in another, when such a translation is possible? What is the computational complexity of determining various properties of computations specified a given formalism?The research proposed here aims to contribute to our understanding of arithmetic circuits---a formalism for specifying computations on sets of natural numbers---focusing primarily on issues of expressive power and computational complexity. Despite their naturalness apparent simplicity, arithmetic circuits pose many unsolved mathematical problems, with intimate connections to a variety of topics in mathematical logic.
Organisations
People |
ORCID iD |
| I Pratt-Hartmann (Principal Investigator) |
Publications
Duentsch, I
(2009)
Complex Algebras of Arithmetic
in FUNDAMENTA INFORMATICAE
Duntsch I
(2009)
Timed Contact Algebras
Düntsch I
(2009)
Complex Algebras of Arithmetic
in Fundamenta Informaticae
Pratt-Hartmann I
(2011)
Functions definable by numerical set-expressions
in Journal of Logic and Computation
Pratt-Hartmann I
(2009)
Mathematical Theory and Computational Practice
| Description | This award covered a Visiting Fellowhip for Prof. I. Duentsch, of Brock University, Ontario, who visited Manchester University for three months in 2009. The research undertaken has contributed to our understanding of arithmetic circuits---a formalism for specifying computations on sets of natural numbers-- focusing primarily on issues of expressive power an decidability. The first main outcome of the investigation was the discovery of various classes of functions that arithmetic circuits cannot define. For example, arithmetic circuits cannot compute sums or products of finite sets of numbers; they cannot compute regressive (roughly: slow-growing) numerical functions; and they cannot test for finiteness (or other basic properties) of sets. This line of research was pursued further by considering the effect of adding some of these undefinable functions as primitive operations: a complex pattern of definability and non-definability results emerged from this further work. On the other hand, surprising examples of circuit-definable sets were found (most notably, the set of Fermat numbers); and it was shown that numerical functions definable by arithmetic circuits can have super-polynomial growth. Thus, arithmetic circuits turn out to be both more and less expressive than might at first have been supposed. The second main outcome of the investigation was to establish a number of technical, algebraic properties of complex algebras over the natural numbers (generated by their additive structure, their multiplicative structure, or both together), and to relate these results to the problems of determining the validity/satisfiability of equations involving arithmetic circuits. |
| Exploitation Route | These results will be of interest to academic researchers in Theoretical Computer Science and Formal Language Theory. |
| Sectors | Digital/Communication/Information Technologies (including Software) |
| URL | http://www.cs.man.ac.uk/~ipratt/ |