Proper complexity function: Difference between revisions
Content deleted Content added
m remove Erik9bot category,outdated, tag and general fixes, added orphan tag |
m Bot: Removing Orphan Tag (Nolonger an Orphan) (Report Errors) |
||
| Line 1: | Line 1: | ||
{{Unreferenced|date=December 2009}} |
{{Unreferenced|date=December 2009}} |
||
{{Orphan|date=December 2009}} |
|||
A '''proper complexity function''' is a function ''f'' mapping a [[natural number]] to a natural number such that: |
A '''proper complexity function''' is a function ''f'' mapping a [[natural number]] to a natural number such that: |
||
* ''f'' is nondecreasing; |
* ''f'' is nondecreasing; |
||
Revision as of 03:15, 9 January 2013
 |
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.