| dbo:abstract |
In complexity theory, a time-constructible function is 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). The purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine. (en) En théorie de la complexité, une fonction constructible en temps est une fonction f des entiers naturels vers les entiers naturels, avec la propriété que f(n) peut être calculée à partir de n par une machine de Turing qui se termine en un temps du même ordre de grandeur que f(n). Le but de cette définition est d'exclure les fonctions qui n'apportent pas de borne supérieure sur le temps d'exécution. Une définition similaire pour la complexité en espace existe et introduit la notion de fonction constructible en espace. (fr) Na teoria da complexidade, uma função tempo-construível é uma função f dos números naturais para números naturais com a propriedade de que f(n) pode ser construída a partir de n por uma máquina de Turing em tempo de ordem f(n). A finalidade de tal definição é excluir funções que não provêm um limitante superior sobre o tempo de execução de alguma máquina de Turing. (pt) 複雜度理論裡，函數時間可構（英語：time constructible），意即存在運行時間規模在內的圖靈機，當輸入時，圖靈機輸出。定義此類函數是為了排除一些無法成為圖靈機運行時間上界的函數。 (zh) |
| dbo:wikiPageID |
906783 (xsd:integer) |
| dbo:wikiPageLength |
4527 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1046791464 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Big-O_notation dbc:Types_of_functions dbr:Space_hierarchy_theorem dbr:Computational_complexity_theory dbc:Computational_complexity_theory dbr:Natural_numbers dbr:Turing_machine dbr:Time_hierarchy_theorem dbr:Little-o_notation |
| dbp:id |
3461 (xsd:integer) |
| dbp:title |
constructible (en) |
| dbp:wikiPageUsesTemplate |
dbt:Reflist dbt:Tmath dbt:PlanetMath_attribution |
| dct:subject |
dbc:Types_of_functions dbc:Computational_complexity_theory |
| gold:hypernym |
dbr:Function |
| rdf:type |
dbo:Disease |
| rdfs:comment |
In complexity theory, a time-constructible function is 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). The purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine. (en) En théorie de la complexité, une fonction constructible en temps est une fonction f des entiers naturels vers les entiers naturels, avec la propriété que f(n) peut être calculée à partir de n par une machine de Turing qui se termine en un temps du même ordre de grandeur que f(n). Le but de cette définition est d'exclure les fonctions qui n'apportent pas de borne supérieure sur le temps d'exécution. Une définition similaire pour la complexité en espace existe et introduit la notion de fonction constructible en espace. (fr) Na teoria da complexidade, uma função tempo-construível é uma função f dos números naturais para números naturais com a propriedade de que f(n) pode ser construída a partir de n por uma máquina de Turing em tempo de ordem f(n). A finalidade de tal definição é excluir funções que não provêm um limitante superior sobre o tempo de execução de alguma máquina de Turing. (pt) 複雜度理論裡，函數時間可構（英語：time constructible），意即存在運行時間規模在內的圖靈機，當輸入時，圖靈機輸出。定義此類函數是為了排除一些無法成為圖靈機運行時間上界的函數。 (zh) |
| rdfs:label |
Constructible function (en) Fonction constructible (fr) Função construível (pt) 可構函數 (zh) |
| owl:sameAs |
freebase:Constructible function wikidata:Constructible function dbpedia-fr:Constructible function dbpedia-he:Constructible function dbpedia-pt:Constructible function dbpedia-zh:Constructible function https://global.dbpedia.org/id/4iQhv |
| prov:wasDerivedFrom |
wikipedia-en:Constructible_function?oldid=1046791464&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Constructible_function |
| is dbo:wikiPageRedirects of |
dbr:Space-constructible_function dbr:Space-constructible dbr:Space_constructible dbr:Time-constructible_function dbr:Time_constructible |
| is dbo:wikiPageWikiLink of |
dbr:List_of_computability_and_complexity_topics dbr:Glossary_of_areas_of_mathematics dbr:Constructibility dbr:Gap_theorem dbr:Space-constructible_function dbr:Fine-grained_reduction dbr:Euler_calculus dbr:Time_hierarchy_theorem dbr:Space-constructible dbr:Space_constructible dbr:Time-constructible_function dbr:Time_constructible |
| is foaf:primaryTopic of |
wikipedia-en:Constructible_function |