This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License
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.
| Property | Value |
|---|---|
| dbo:abstract |
|
| dbo:wikiPageID |
|
| dbo:wikiPageLength |
|
| dbo:wikiPageRevisionID |
|
| dbo:wikiPageWikiLink | |
| dbp:wikiPageUsesTemplate | |
| dcterms:subject | |
| gold:hypernym | |
| rdf:type | |
| rdfs:comment |
|
| rdfs:label |
|
| owl:sameAs | |
| prov:wasDerivedFrom | |
| foaf:isPrimaryTopicOf | |
| is dbo:wikiPageWikiLink of | |
| is foaf:primaryTopic of |