La thèse de Cobham - Cobham's thesis

La thèse de Cobham , également connue sous le nom de thèse de Cobham-Edmonds (du nom d' Alan Cobham et Jack Edmonds ), affirme que les problèmes de calcul ne peuvent être calculés sur un appareil de calcul que s'ils peuvent être calculés en temps polynomial ; c'est-à-dire s'ils appartiennent à la classe de complexité P . En termes modernes, il identifie des problèmes traitables avec la classe de complexité P .

Formellement, dire qu'un problème peut être résolu en temps polynomial revient à dire qu'il existe un algorithme qui, étant donné une instance de n bits du problème en entrée, peut produire une solution en temps O( n ^c ), la lettre O est une notation big-O et c est une constante qui dépend du problème mais pas de l'instance particulière du problème.

L'article d'Alan Cobham de 1965 intitulé « La difficulté intrinsèque de calcul des fonctions » est l'une des premières mentions du concept de la classe de complexité P , consistant en des problèmes décidables en temps polynomial. Cobham a théorisé que cette classe de complexité était une bonne façon de décrire l'ensemble des réalistement calculables problèmes.

L'article de 1965 de Jack Edmonds "Chemins, arbres et fleurs" est également crédité d'avoir identifié P avec des problèmes traitables.

Limites

Le graphique montre le temps de résolution du problème en millisecondes (ms) par rapport à la taille du problème, n, pour les problèmes de sac à dos résolus par un algorithme spécialisé de pointe utilisant un ordinateur Pentium III à 933 MHz (moyenne de 100 instances, données de :). L'ajustement de l'équation quadratique suggère que la complexité algorithmique empirique pour les instances avec 50 à 10 000 variables est O((log  n ) ² ) malgré une estimation de complexité exponentielle dans le pire des cas en théorie.

Alors que la thèse de Cobham est une étape importante dans le développement de la théorie de la complexité computationnelle , elle a des limites appliquées à la faisabilité pratique des algorithmes. La thèse stipule essentiellement que " P " signifie " facile, rapide et pratique ", tandis que " pas dans P " signifie " difficile, lent et peu pratique ". Mais ce n'est pas toujours vrai, car la thèse fait abstraction de certaines variables importantes qui influencent le temps d'exécution dans la pratique :

• Il ignore les facteurs constants et les termes d'ordre inférieur.
• Il ignore la taille de l'exposant. Le théorème de la hiérarchie temporelle prouve l'existence de problèmes dans P nécessitant des exposants arbitrairement grands.
• Il ignore la taille typique de l'entrée.

Tous les trois sont liés et constituent des plaintes générales concernant l' analyse des algorithmes , mais ils s'appliquent particulièrement à la thèse de Cobham puisqu'elle fait une affirmation explicite sur l'aspect pratique. Selon la thèse de Cobham, un problème pour lequel le meilleur algorithme prend n ²⁰⁰ instructions est considéré comme réalisable, et un problème avec un algorithme qui prend 2 ^{0,00001 n} instructions infaisable, même si on ne pourrait jamais résoudre une instance de taille n = 2 avec l'ancien algorithme , alors qu'une instance de ce dernier problème de taille n = 10 ⁶ pourrait être résolue sans difficulté. Dans les domaines où des problèmes pratiques ont des millions de variables (telles que la recherche opérationnelle ou Electronic Design Automation ), même O ( n ³ algorithmes) sont souvent peu pratique.

Les références