Thèse de Cobham

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.