Loading AI tools
De Wikipédia, l'encyclopédie libre
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) [2],[3],[4], 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[5].
L'article d'Alan Cobham (1965) s'appelle The intrinsic computational difficulty of functions[6] 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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.