Back Tesis de Cobham Spanish Thèse de Cobham French Teza Edmondsa Polish Tese de Cobham Portuguese

Cobham's thesis

Not to be confused with Cobham's theorem.

Cobham's thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds),[1][2][3] 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.[4] 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"[5] 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"[6] is also credited with identifying P with tractable problems.[7]

  1. ^ Oded Goldreich (2008), Computational complexity: a conceptual perspective, Cambridge University Press, p. 128, ISBN 978-0-521-88473-0.
  2. ^ Dexter Kozen (2006), Theory of computation, Birkhäuser, p. 4, ISBN 978-1-84628-297-3.
  3. ^ Egon Börger (1989), Computability, complexity, logic, Elsevier, p. 225, ISBN 978-0-444-87406-1.
  4. ^ Homer, Steven; Selman, Alan L. (1992), "Complexity Theory", in Kent, Alan; Williams, James G. (eds.), Encyclopedia of Computer Science and Technology, vol. 26, CRC Press.
  5. ^ Alan Cobham (1965), The intrinsic computational difficulty of functions (PDF).
  6. ^ Edmonds, Jack (1965). "Paths, trees, and flowers". Can. J. Math. 17: 449–467. doi:10.4153/CJM-1965-045-4. S2CID 18909734.
  7. ^ Meurant, Gerard (2014). Algorithms and Complexity. Elsevier. p. p. 4. ISBN 978-0-08093391-7. A problem is said to be feasible if it can be solved in polynomial time (as stated for the first time in Edmonds [26] [1965, Paths, trees, and flowers]).

Rich TVX News Network Site

Rich TVX News Network Info

© MMXXIII Rich X Search. We shall prevail. All rights reserved. Rich X Search