About: Constructible function

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Constructible function Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : prod-dbpedia.inria.fr associated with source document(s)

Attributes	Values
rdfs:label	Constructible function (en) Fonction constructible (fr)
rdfs:comment	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)
sameAs	Constructible function Constructible function Constructible function Constructible function Constructible function Constructible function Constructible function
Wikipage page ID	8556490 (xsd:integer)
Wikipage revision ID	164702532 (xsd:integer)
dbo:wikiPageWikiLink	category-fr:Propriété_de_fonction category-fr:Théorie_de_la_complexité_des_algorithmes Big O notation Space complexity Time complexity dbpedia-fr:Démonstration_constructive Natural number General recursive function Turing machine Law of excluded middle dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) dbpedia-fr:Théorème_de_hiérarchie_en_temps_déterministe
page length (characters) of wiki page	5982 (xsd:nonNegativeInteger)
dct:subject	category-fr:Propriété_de_fonction category-fr:Théorie_de_la_complexité_des_algorithmes
prop-fr:wikiPageUsesTemplate	dbpedia-fr:Modèle:Autre4 dbpedia-fr:Modèle:Lien dbpedia-fr:Modèle:Palette dbpedia-fr:Modèle:Portail dbpedia-fr:Modèle:Références dbpedia-fr:Modèle:Computational_Complexity_(Arora_et_Barak) dbpedia-fr:Modèle:Complexité_algorithmique_(Perifel)
prov:wasDerivedFrom	wikipedia-fr:Fonction_constructible?oldid=164702532&ns=0
prop-fr:fr	théorème de hiérarchie en espace (fr) théorème de la lacune (fr)
prop-fr:lang	en (fr)
prop-fr:trad	Space hierarchy theorem (fr) Gap theorem (fr)
foaf:isPrimaryTopicOf	wikipedia-fr:Fonction_constructible
has abstract	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)
is dbo:wikiPageWikiLink of	Constructibility DSPACE DTIME dbpedia-fr:Lexique_de_propriétés_de_fonctions Turing machine NSPACE NTIME dbpedia-fr:Théorème_de_hiérarchie_en_temps_déterministe
is Wikipage disambiguates of	Constructibility
is oa:hasTarget of	En labels Wikidata Fr related
is foaf:primaryTopic of	wikipedia-fr:Fonction_constructible

Faceted Search & Find service v1.16.111 as of Oct 19 2022

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3234 as of May 18 2022, on Linux (x86_64-ubuntu_bionic-linux-gnu), Single-Server Edition (39 GB total memory, 13 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software