Proper complexity function: Difference between revisions
Content deleted Content added
m Bot: Removing Orphan Tag (Nolonger an Orphan) (Report Errors) |
Vivalawombat (talk | contribs) No edit summary Tag: gettingstarted edit |
||
| Line 10: | Line 10: | ||
{{DEFAULTSORT:Proper Complexity Function}} |
{{DEFAULTSORT:Proper Complexity Function}} |
||
[[Category:Computational complexity theory]] |
[[Category:Computational complexity theory]] |
||
<ref>Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography. Birkhäuser Verlag, 2008, p.28 </ref> |
|||
Revision as of 13:53, 6 May 2014
 |
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. [1]
- ^ Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography. Birkhäuser Verlag, 2008, p.28