Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Proper_complexity_function> ?p ?o. }
Showing items 1 to 12 of
12
with 100 items per page.
- Proper_complexity_function abstract "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 function, space-constructible function, and time-constructible function.".
- Proper_complexity_function wikiPageID "2908475".
- Proper_complexity_function wikiPageRevisionID "532101847".
- Proper_complexity_function hasPhotoCollection Proper_complexity_function.
- Proper_complexity_function subject Category:Computational_complexity_theory.
- Proper_complexity_function comment "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 function, space-constructible function, and time-constructible function.".
- Proper_complexity_function label "Proper complexity function".
- Proper_complexity_function sameAs m.08bvyx.
- Proper_complexity_function sameAs Q7250173.
- Proper_complexity_function sameAs Q7250173.
- Proper_complexity_function wasDerivedFrom Proper_complexity_function?oldid=532101847.
- Proper_complexity_function isPrimaryTopicOf Proper_complexity_function.