Ramification, Recursion & Arithmetic
- DIMACS Center - Room 431
- Busch Campus
- Piscataway, New Jersey
- January 26, 2:30 P.M.
The traditional approach to computational complexity has been to
identify resources consumed by a computer and to bound these
asymptotically. When complexity notions are adapted to recursion
theory and arithmetic, the idea of bounded resources is often translated
into bounds on the binary length of various terms. However, this
approach makes the formalisms complicated, conceals the interaction
of recursion or induction with computational complexity, and conflicts
with the idea of numbers as abstract, dimensionless entitites.
The theme of the presentation is how ramification --- the layering of
recursion, induction, or knowledge --- is connected to computational
complexity. Using ramification, explicit bounding terms are eliminated.
Simple structures emerge that are quite similar to those well known
from `infeasible' mathematics, but that have limited computational
complexity. I will describe results to date in ramified recursion,
and outline how this approach can be applied to first order arithmetic.