Proper complexity function
≈ 1 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A proper complexity function is a function f mapping natural numbers to natural numbers 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. Similar notions include honest functions, space-constructible functions, and time-constructible functions.
A proper complexity function is a function f mapping natural numbers to natural numbers 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. Similar notions include honest functions, space-constructible functions, and time-constructible functions. ==References==
Text derived from https://en.wikipedia.org/w/index.php?oldid=1300380874 under CC BY-SA 4.0; modifications have been made.