Difference between revisions of "Complexity Zoo:K"

From Complexity Zoo
Jump to: navigation, search
(No class starting with K? Must fix that.)
 
m (1 revision: Complexity zoo import.)
 

Latest revision as of 22:10, 17 November 2012

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References


Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform


K


[edit] K: Feasibly recursive functions

A class of number-theoretic functions, defined as the closure of basic integer arithmetic operations (+, -, \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 UD-uniform FTC0 by [Hes01].

Personal tools

Variants
Actions
Navigation
Toolbox