Proper complexity function: Difference between revisions
Content deleted Content added
not unreferenced |
m WP:CHECKWIKI error fix for #52. Do general fixes if a problem exists. - using AWB |
||
| Line 7: | Line 7: | ||
Similar notions include honest function, [[space-constructible function]], and [[time-constructible function]]. |
Similar notions include honest function, [[space-constructible function]], and [[time-constructible function]]. |
||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
==References== |
==References== |
||
{{Reflist}} |
{{Reflist}} |
||
| ⚫ | |||
| ⚫ | |||
Revision as of 22:30, 23 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.
References
- ^ Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography. Birkhäuser Verlag, 2008, p.28