Jump to content

Proper complexity function

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by 199.60.7.231 (talk) at 22:39, 14 October 2005. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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)) spaces, and output s f(n) consecutive blanks.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Proper_complexity_function&oldid=25540100"