Alan Cobham（1927－2011）在1965年的文章“The Intrinsic Computational Difficulty of Functions”中最早提出“多项式时间复杂度问题类P”，Cook在其1971年的著名论文“The complexity of theorem proving procedures”中引用，被认为是计算复杂性理论的重要论文之一，由此有所谓的“Cobham论题”（https://en.wikipedia.org/wiki/Cobham%27s_thesis）：

Cobham's thesis, also known as Cobham–Edmonds thesis 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(n^c), where c is a constant that depends on the problem but not the particular instance of the problem.

上述文章是Cobham在1964年的“International Congress for Logic, Methodology, and the Philosophy of Science”大会发言，他以“乘法比加法难吗？”问题开头：

－The subject of my talk is perhaps most directly indicated by simply asking two questions: first, is it harder to multiply than to add? and second, why?

接着他提出“元数字分析（metanumerical-analysis）”，表明此方法用于分析独立于任何具体的计算方法的问题：

－ So in metanumerical-analysis we encounter problems related to specific computational systems or categories of computing machines as well as problems such as those mentioned above which, though concerned with computation, are independent of any particular method of computation.

Cobham从“Grzegorczyk层次”出发（https://en.wikipedia.org/wiki/Grzegorczyk_hierarchy），Grzegorczyk层次是对原始递归函数的分类：

S^0 includes functions such as x+1, x+2,…

S^1 includes functions such as x+y, 4x,…

S^2 includes functions such as xy, x^4,…

S^3 includes functions such as x^y, 2^2^2^x,…

。。。

Cobham将递归函数与计算复杂性相联系，提出时间复杂度TIME(n)和空间复杂度SPACE(n)：

－With each single-tape Turing machine Z which computers a function of one variable we may associate two functions, TIME(n) and SPACE(n). Assuming some standard encoding of natural numbers - we might take decimal notation to be specific - we define TIME(n), where n is a natural number, to be the number of steps (instruction executions) in the computation on Z starting with n encoded on its tape, and define SPACE(n) to be the number of distinct tape squares scanned during the course of this computation.

Cobham通过一个定理指出：指数形式的函数（S^k，k>=3）具有指数形式的时间复杂度和空间复杂度后，就集中在讨论具有多项式形式的函数集合（S^2）：

－This leaves us some latitude for differentiating among functions in S^2. The closest analog of the foregoing theorem concerning TIME(n), rather than SPACE(n), that I know of states that for any f in S^2 there exists a Turing machine Z which computes it and such that TIME(n) is bounded by a polynomial in its argument.

最后，Cobham提出了“多项式时间复杂度问题类P”的概念：

- We find that it makes a definite difference what class of computational methods and devices we consider in our attempt to formalize the definition （of a feasibly computable function）. … The problem is reminiscent of, and obviously closely related to, that of the formalization of the notion of « effectiveness ». But the emphasis is different in that the physical aspects of the computation process are here of predominant concerne. The question of what may legitimately be considered to constitute a step of a computation is quite unlike that of what constitutes an effective operation … If we are to make fine distinctions, say between [TIME(n)] and [TIME(n^2)], then we must have an equally fine analysis of all phases of the computational process… We must be prepared to argue that we haven’t taken too broad a class for [TIME(n)] and thus admitted to it functions not in actuality computable in a number of steps linearly bounded by the lengths of its arguments.

总之，Cobham的这篇文章提出的诸议题：乘法与加法的相对难度，计算的原始步骤，可计算函数的层次等，在深入研究可计算性理论和计算复杂性理论的今天，会继续启发人们，。。。

References

[1] A. Cobham, The intrinsic computational difficulty of functions, in Y. Bar-Hillel, ed., Logic, Methodology and Philosophy of Science: Proceedings of the 1964 International Congress, North-Holland Publishing Company, Amsterdam, 1965, pp. 24-30.（https://www.cs.toronto.edu/~sacook/homepage/cobham_intrinsic.pdf）

[2] The Complexity of Theorem Proving Procedures. Proceedings Third Annual ACM Symposium on Theory of Computing, May 1971, pp 151-158. （https://www.cs.toronto.edu/~sacook/homepage/1971.pdf）