Jump to content

Proper complexity function

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Thatsme314 (talk | contribs) at 02:40, 6 April 2022 (grammar). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.

[1]

References

  1. ^ Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography. Birkhäuser Verlag, 2008, p.28
Retrieved from "https://en.wikipedia.org/w/index.php?title=Proper_complexity_function&oldid=1081224188"