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].

Le graphique montre le temps en millisecondes pour résoudre des instances du problème du sac à dos en fonction de la taille d'entrée n. L'expérience a été réalisée sur un ordinateur Pentium III 933 MHz (les données proviennent d'une moyenne sur 100 instances à chaque fois^[1]).

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.