Constructible function
http://dbpedia.org/resource/Constructible_function an entity of type: Disease
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
複雜度理論裡，函數時間可構（英語：time constructible），意即存在運行時間規模在內的圖靈機，當輸入時，圖靈機輸出。定義此類函數是為了排除一些無法成為圖靈機運行時間上界的函數。
rdf:langString
rdf:langString
Constructible function
rdf:langString
Fonction constructible
rdf:langString
Função construível
rdf:langString
可構函數
xsd:integer
906783
xsd:integer
1046791464
xsd:integer
3461
rdf:langString
constructible
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
複雜度理論裡，函數時間可構（英語：time constructible），意即存在運行時間規模在內的圖靈機，當輸入時，圖靈機輸出。定義此類函數是為了排除一些無法成為圖靈機運行時間上界的函數。
xsd:nonNegativeInteger
4527