Class Description

K: Feasibly recursive functions

A class of number-theoretic functions, defined as the closure of basic integer arithmetic operations (, as well as constants 0, 1, and projections) under composition and polynomially long sums and products. Defined by [Con73], who mistakenly claimed it coincides with FP.

Equals UD-uniform FTC0 by [Hes01].

Linked From

No class.