Proper complexity function: Difference between revisions
Content deleted Content added
Thatsme314 (talk | contribs) m grammar |
Thatsme314 (talk | contribs) formatting |
||
| Line 6: | Line 6: | ||
Similar notions include honest functions, [[space-constructible function]]s, and [[time-constructible function]]s. |
Similar notions include honest functions, [[space-constructible function]]s, and [[time-constructible function]]s. |
||
<ref>Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography. Birkhäuser Verlag, 2008, p.28</ref> |
|||
==References== |
==References== |
||
{{Reflist}} |
{{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}} |
{{DEFAULTSORT:Proper Complexity Function}} |
||
Latest revision as of 03:16, 6 April 2022
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 functions, space-constructible functions, and time-constructible functions.
References
[edit]Myashnikov, Alexei; Shpilrain, Vladimir; Ushakov, Vladimir (2008). Group-based Cryptography. Birkhauser. p. 28. ISBN 978-3-7643-8826-3.