| dbo:abstract
|
- 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. (en)
- En ciencias de la computación, la tesis de Cobham, también conocida como la tesis de Cobham-Edmonds (llamada así por Alan Cobham y Jack Edmonds) afirma que los problemas tratables o "fácilmente computables" son los problemas computables en tiempo polinómico. En particular, los problemas de decisión “fácilmente” computables son los de clase P . Esta tesis es importante porque la clase P es precisamente una clase que no es sensible a los detalles de un modelo computacional; por ejemplo, una máquina de Turing de una o varias bandas da la misma definición de la clase P. El artículo de Alan Cobham (1965) se llama La dificultad computacional intrínseca de las funciones y es una de las primeras apariciones de la clase P, que consiste en problemas decidibles en tiempo polinómico. Cobham teorizó que esta clase de complejidad era una buena forma de describir el conjunto de problemas factiblemente computables. Al artículo de Jack Edmonds de 1965 "Caminos, árboles y flores" también se le atribuye la identificación de P con problemas tratables. Esta tesis ha sido criticada porque no tiene en cuenta el exponente del polinomio en absoluto, pero según el teorema de la jerarquía temporal determinista, existen problemas cuyo mejor algoritmo tiene un exponente arbitrariamente grande. (es)
- 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), 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. L'article d'Alan Cobham (1965) s'appelle The intrinsic computational difficulty of functions 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. (fr)
- Teza Edmondsa, znana również jako teza Cobhama-Edmondsa (od i ), stwierdza, że dany problem obliczeniowy jest praktycznie obliczalny przez jakieś urządzenie obliczeniowe wtedy i tylko wtedy, gdy istnieje algorytm obliczający go w czasie wielomianowym; to znaczy, gdy problem ten leży w zasięgu klasy złożoności P. Formalnie, powiedzieć, że problem można rozwiązać w czasie wielomianowym znaczy, że istnieje algorytm, który, przyjmując n-bitową instancję problemu na wejściu, zwraca rozwiązanie w czasie O(nc), gdzie c jest stałą, zależną od typu problemu (ale nie od jego konkretnej instancji). Jack Edmonds był jednym z twórców dziedziny optymalizacji kombinatorycznej. Jego artykuł z 1965 roku zatytułowany "Paths, trees, and flowers" był jednym z pierwszych dokumentów sugerujących możliwość ustanowienia matematycznej teorii efektywnych algorytmów kombinatorycznych. W artykule tym Edmonds postawił również tezę, jakoby klasa złożoności P stanowiła dobrą reprezentację zbioru problemów . (pl)
- A Tese de Cobham, também conhecida como a tese de Cobham–Edmonds (assim denominada em referência a Alan Cobham e Jack Edmonds), assegura que problemas computacionais podem ser resolvidos de maneira viável em algum dispositivo de computação apenas se forem computáveis em tempo polinomial, ou seja, se pertencerem à classe de complexidade P. Formalmente, para dizer que um problema pode ser resolvido em tempo polinomial significa dizer que existe um algoritmo que, dado uma instância de um problema de n bits como entrada, pode produzir uma solução em tempo O(nc), onde c é uma constante que depende do problema mas não da instância particular do problema. O artigo de 1965 de Alan Cobham intitulado "The intrinsic computational difficulty of functions" (em português: A dificuldade computacional intrínseca das funções) é uma das menções mais antigas da classe de complexidade P, consistindo de problemas decidíveis em tempos polinomiais. Cobham teorizou que essa classe de complexidade era uma boa maneira de descrever o conjunto de problemas computáveis em tempo razoável. Qualquer problema que não pode estar em P não é razoável, mas se um problema do mundo real poder ser resolvido por um algoritmo existente em P, geralmente tal algoritmo será eventualmente descoberto. A classe P é um objeto de estudo útil porque ela não é sensível aos detalhes do modelo de computação: por exemplo, uma mudança de uma máquina de Turing de uma única fita para uma máquina multifita pode trazer um aumento de velocidade quadrático, mas qualquer algoritmo que rode em tempo polinomial em um modelo também fará o mesmo no outro. De modo similar, a classe de complexidade NC pode ser pensada como a classe de problemas "efetivamente solúveis" em um computador paralelo. (pt)
|
| rdfs:comment
|
- 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. Jack Edmonds's 1965 paper "Paths, trees, and flowers" is also credited with identifying P with tractable problems. (en)
- En ciencias de la computación, la tesis de Cobham, también conocida como la tesis de Cobham-Edmonds (llamada así por Alan Cobham y Jack Edmonds) afirma que los problemas tratables o "fácilmente computables" son los problemas computables en tiempo polinómico. En particular, los problemas de decisión “fácilmente” computables son los de clase P . Esta tesis es importante porque la clase P es precisamente una clase que no es sensible a los detalles de un modelo computacional; por ejemplo, una máquina de Turing de una o varias bandas da la misma definición de la clase P. (es)
- 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), 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. L'article d'Alan Cobham (1965) s'appelle The intrinsic computational difficulty of functions et est l'une des premières occurrences de la classe P. (fr)
- Teza Edmondsa, znana również jako teza Cobhama-Edmondsa (od i ), stwierdza, że dany problem obliczeniowy jest praktycznie obliczalny przez jakieś urządzenie obliczeniowe wtedy i tylko wtedy, gdy istnieje algorytm obliczający go w czasie wielomianowym; to znaczy, gdy problem ten leży w zasięgu klasy złożoności P. Formalnie, powiedzieć, że problem można rozwiązać w czasie wielomianowym znaczy, że istnieje algorytm, który, przyjmując n-bitową instancję problemu na wejściu, zwraca rozwiązanie w czasie O(nc), gdzie c jest stałą, zależną od typu problemu (ale nie od jego konkretnej instancji). (pl)
- A Tese de Cobham, também conhecida como a tese de Cobham–Edmonds (assim denominada em referência a Alan Cobham e Jack Edmonds), assegura que problemas computacionais podem ser resolvidos de maneira viável em algum dispositivo de computação apenas se forem computáveis em tempo polinomial, ou seja, se pertencerem à classe de complexidade P. De modo similar, a classe de complexidade NC pode ser pensada como a classe de problemas "efetivamente solúveis" em um computador paralelo. (pt)
|
