| http://dbpedia.org/ontology/abstract
|
A proper complexity function is a function … 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.nctions, and time-constructible functions.
|
| http://dbpedia.org/ontology/wikiPageID
|
2908475
|
| http://dbpedia.org/ontology/wikiPageLength
|
956
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1081227362
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Natural_number +
, http://dbpedia.org/resource/Time-constructible_function +
, http://dbpedia.org/resource/Space-constructible_function +
, http://dbpedia.org/resource/Turing_machine +
, http://dbpedia.org/resource/Category:Computational_complexity_theory +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Cite_book +
, http://dbpedia.org/resource/Template:Reflist +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Computational_complexity_theory +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Function +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Proper_complexity_function?oldid=1081227362&ns=0 +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Proper_complexity_function +
|
| owl:sameAs |
https://global.dbpedia.org/id/4tT6u +
, http://www.wikidata.org/entity/Q7250173 +
, http://dbpedia.org/resource/Proper_complexity_function +
, http://rdf.freebase.com/ns/m.08bvyx +
|
| rdf:type |
http://dbpedia.org/ontology/Disease +
|
| rdfs:comment |
A proper complexity function is a function … 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.nctions, and time-constructible functions.
|
| rdfs:label |
Proper complexity function
|
