<p>You can try to look at the paper <a href="https://doi.org/10.1007/BF01201998" rel="nofollow noreferrer" title="Comput Complexity 2, 97–110 (1992)">A new recursion-theoretic characterization of the polytime functions</a> by Stephen Bellantoni and Stephen Cook, which has very nice discussion on Cobham's polynomial-time characterization in the introduction section. This paper also has pointers to other related works. You can easily find the paper somewhere on the web in case you are not subscribed to Springer.</p>

CC BY-SA 4.0
2010-09-29T19:03:20.113Z
2022-11-22T08:26:23.560Z
2022-11-22T08:26:23.560Z
Dai Le
<p>In the following paper:</p>

<p>Alan Cobham (1965), "The intrinsic computational difficulty of functions", <em>Proc. Logic, Methodology, and Philosophy of Science II</em>, North Holland.</p>

<p>Cobham defined the class <strong>P</strong> as the class for efficient computations. He stated that his notion is machine-independent.</p>

<p>Unfortunately, I don't have access to this paper. Can anyone clarify the points he made there? Is it just a thesis, or something proved?</p>

CC BY-SA 2.5
2010-09-29T18:50:30.020Z
AFAIK, he defined the class $P$ as the smallest set of functions containing some simple initial functions, closed under composition, and bounded recursion on notation. It is machine independent in the sense that it is a logical characterization similar to the definition of primitive recursive functions, it does not mention any machines.
Kaveh
<cc.complexity-theory><complexity-classes>
Cobham's Result on Efficient Computations
Rahab
# Cobham's Result on Efficient Computations

(Asked by: username_0 on 2010-09-29)

In the following paper:

Alan Cobham (1965), "The intrinsic computational difficulty of functions", *Proc. Logic, Methodology, and Philosophy of Science II*, North Holland.

Cobham defined the class **P** as the class for efficient computations. He stated that his notion is machine-independent.

Unfortunately, I don't have access to this paper. Can anyone clarify the points he made there? Is it just a thesis, or something proved?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: AFAIK, he defined the class $P$ as the smallest set of functions containing some simple initial functions, closed under composition, and bounded recursion on notation. It is machine independent in the sense that it is a logical characterization similar to the definition of primitive recursive functions, it does not mention any machines.  

---

## 1 answers

### Answer by username_2 on 2010-09-29. Score: 9 | Accepted answer

You can try to look at the paper [A new recursion-theoretic characterization of the polytime functions](https://doi.org/10.1007/BF01201998 "Comput Complexity 2, 97–110 (1992)") by Stephen Bellantoni and Stephen Cook, which has very nice discussion on Cobham's polynomial-time characterization in the introduction section. This paper also has pointers to other related works. You can easily find the paper somewhere on the web in case you are not subscribed to Springer.


---

