Proper complexity function
Encyclopedia
A proper complexity function is a function f mapping a natural number
to a natural number such that:
If f and g are two proper complexity functions, then f + g, fg, and 2f, are also proper complexity functions.
Similar notions include honest function, space-constructible function, and time-constructible function.
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
to a natural number such that:
- f is nondecreasing;
- there exists a k-string Turing machineTuring machineA Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
M such that on any input of length n, M halts after O(n + f(n)) steps, uses O(f(n)) space, and outputs f(n) consecutive blanks.
If f and g are two proper complexity functions, then f + g, fg, and 2f, are also proper complexity functions.
Similar notions include honest function, space-constructible function, and time-constructible function.