Stephen Bellantoni

Ramification, Recursion & Arithmetic

DIMACS Center - Room 431

Busch Campus

Piscataway, New Jersey

January 26, 2:30 P.M.

Abstract:

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.