View source for Proper complexity function

A '''proper complexity function''' is a function ''f'' mapping a [[Natural number|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''&nbsp;+&nbsp;''g'', ''fg'', and 2<sup>''f''</sup> are also proper complexity functions.

Similar notions include honest functions, space-constructible functions, and time-constructible functions.

==References==
{{Reflist}}
{{cite book |last1=Myashnikov |first1=Alexei |last2=Shpilrain |first2=Vladimir |last3=Ushakov |first3=Vladimir |title=Group-based Cryptography |date=2008 |publisher=Birkhauser |isbn=978-3-7643-8826-3 |page=28}}

{{DEFAULTSORT:Proper Complexity Function}}
[[Category:Computational complexity theory]]

{{Sourceattribution|Proper complexity function}}