Concept

Thèse de Cobham

Cobham's thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds), asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is, if they lie in the complexity class P. In modern terms, it identifies tractable problems with the complexity class P. Formally, to say that a problem can be solved in polynomial time is to say that there exists an algorithm that, given an n-bit instance of the problem as input, can produce a solution in time O(nc), using the big-O notation and with c being a constant that depends on the problem but not the particular instance of the problem. Alan Cobham's 1965 paper entitled "The intrinsic computational difficulty of functions" is one of the earliest mentions of the concept of the complexity class P, consisting of problems decidable in polynomial time. Cobham theorized that this complexity class was a good way to describe the set of feasibly computable problems. Jack Edmonds's 1965 paper "Paths, trees, and flowers" is also credited with identifying P with tractable problems. While Cobham's thesis is an important milestone in the development of the theory of computational complexity, it has limitations as applied to practical feasibility of algorithms. The thesis essentially states that "P" means "easy, fast, and practical", while "not in P" means "hard, slow, and impractical". But this is not always true, because the thesis abstracts away some important variables that influence the runtime in practice: It ignores constant factors and lower-order terms. It ignores the size of the exponent. The time hierarchy theorem proves the existence of problems in P requiring arbitrarily large exponents. It ignores the typical size of the input. All three are related and are general complaints about analysis of algorithms, but they particularly apply to Cobham's thesis, since it makes an explicit claim about practicality.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.