Class Description

K: Feasibly recursive functions

A class of number-theoretic functions, defined as the closure of basic integer arithmetic operations (${\displaystyle +,-,\cdot ,\lfloor x/y\rfloor }$, 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 U_D-uniform FTC⁰ by [Hes01].

Linked From

No class.