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.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Constructible function (en)
- Fonction constructible (fr)
- Função construível (pt)
- 可構函數 (zh)
|
| 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)
|
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| id
| |
| title
| |
| has 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)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)