| Property |
Value |
| dbo:abstract
|
- En informatique, la thèse de Cobham, aussi connue sous la thèse de Cobham–Edmonds (nommée d'après Alan Cobham et Jack Edmonds), postule que les problèmes calculables « facilement » sont les problèmes calculables en temps polynomial. En particulier, les problèmes de décision calculables « facilement » sont ceux de la classe P. L'article d'Alan Cobham (1965) s'appelle The intrinsic computational difficulty of functions et est l'une des premières occurrences de la classe P. Cette thèse est importante car la classe P est justement une classe qui n'est pas sensible aux détails d'un modèle de calcul : par exemple une machine de Turing à une bande ou à plusieurs bandes donne la même définition de la classe P. Cette thèse a été critiquée, car elle ne prend pas du tout en compte l'exposant du polynôme, or d'après le théorème de hiérarchie en temps déterministe, il existe des problèmes dont le meilleur algorithme a un exposant arbitrairement grand. (fr)
- En informatique, la thèse de Cobham, aussi connue sous la thèse de Cobham–Edmonds (nommée d'après Alan Cobham et Jack Edmonds), postule que les problèmes calculables « facilement » sont les problèmes calculables en temps polynomial. En particulier, les problèmes de décision calculables « facilement » sont ceux de la classe P. L'article d'Alan Cobham (1965) s'appelle The intrinsic computational difficulty of functions et est l'une des premières occurrences de la classe P. Cette thèse est importante car la classe P est justement une classe qui n'est pas sensible aux détails d'un modèle de calcul : par exemple une machine de Turing à une bande ou à plusieurs bandes donne la même définition de la classe P. Cette thèse a été critiquée, car elle ne prend pas du tout en compte l'exposant du polynôme, or d'après le théorème de hiérarchie en temps déterministe, il existe des problèmes dont le meilleur algorithme a un exposant arbitrairement grand. (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3388 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- En informatique, la thèse de Cobham, aussi connue sous la thèse de Cobham–Edmonds (nommée d'après Alan Cobham et Jack Edmonds), postule que les problèmes calculables « facilement » sont les problèmes calculables en temps polynomial. En particulier, les problèmes de décision calculables « facilement » sont ceux de la classe P. L'article d'Alan Cobham (1965) s'appelle The intrinsic computational difficulty of functions et est l'une des premières occurrences de la classe P. (fr)
- En informatique, la thèse de Cobham, aussi connue sous la thèse de Cobham–Edmonds (nommée d'après Alan Cobham et Jack Edmonds), postule que les problèmes calculables « facilement » sont les problèmes calculables en temps polynomial. En particulier, les problèmes de décision calculables « facilement » sont ceux de la classe P. L'article d'Alan Cobham (1965) s'appelle The intrinsic computational difficulty of functions et est l'une des premières occurrences de la classe P. (fr)
|
| rdfs:label
|
- Tese de Cobham (pt)
- Thèse de Cobham (fr)
- Tese de Cobham (pt)
- Thèse de Cobham (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
