Cobham's thesis
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. 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), where c is a constant that depends on the problem but not the particular instance of the problem.
primaryTopic
Cobham's thesis
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. 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), where c is a constant that depends on the problem but not the particular instance of the problem.
has abstract
A Tese de Cobham, também conhe ...... is" em um computador paralelo.
@pt
Cobham's thesis, also known as ...... feasibly computable problems.
@en
En informatique, la thèse de C ...... ême définition de la classe P.
@fr
thumbnail
Wikipage page ID
Wikipage revision ID
740,784,640
comment
A Tese de Cobham, também conhe ...... is" em um computador paralelo.
@pt
Cobham's thesis, also known as ...... cular instance of the problem.
@en
En informatique, la thèse de C ...... es occurrences de la classe P.
@fr
label
Cobham's thesis
@en
Tese de Cobham
@pt
Thèse de Cobham
@fr