time-constructible function

English

Noun

time-constructible function (countable and uncountable, plural time-constructible functions)

  1. (computational complexity theory) A function f from natural numbers to natural numbers with the property that f(n) can be constructed from n by a Turing machine in the time of order f(n), whose purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.
This article is issued from Wiktionary. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.