Proper complexity function: Difference between revisions

Content deleted Content added

Inline

Revision as of 02:40, 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 2^f are also proper complexity functions.

^ Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography. Birkhäuser Verlag, 2008, p.28

@@ Line 3: / Line 3: @@
 * 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.
+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 function, [[space-constructible function]], and [[time-constructible function]].
+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>