Proper complexity function: Difference between revisions
Content deleted Content added
m Removed broken link for honest function. |
|||
| Line 5: | Line 5: | ||
If ''f'' and ''g'' are two proper complexity functions, then ''f'' + ''g'', ''fg'', and 2<sup>''f''</sup>, are also proper complexity functions. |
If ''f'' and ''g'' are two proper complexity functions, then ''f'' + ''g'', ''fg'', and 2<sup>''f''</sup>, are also proper complexity functions. |
||
Similar notions include |
Similar notions include honest function, [[space-constructible function]], and [[time-constructible function]]. |
||
[[Category:Computational complexity theory]] |
[[Category:Computational complexity theory]] |
||
Revision as of 23:57, 27 October 2009
A proper complexity function is a function f mapping a natural number to a natural number such that:
- f is nondecreasing;
- there exists a k-string Turing machine 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.