(Updated version of Computational Intractability: A Guide to Algorithmic Lower Bound by Demaine-Gasarch-Hajiaghayi is here)
Any question like who first though of X is often hard to answer. I blogged about who first came up with the Fib numbers here. I've heard rumors that IBM had search engines way before Google but could not figure out how to make money off of it. There are other examples.
I had learned that Cobham defined P in the paper The intrinsic computational difficulty of functions, in 1965. It was The conference on Logic, Methodology, and Philosophy of Science. The paper is here. Jack Edmonds had the notion of P in the paper Paths, Trees, and Flowers here in 1965.
While it is true that Cobham defined P in that paper, and he might have been the first one to do so, was the notion somehow around earlier. I first thought the answer was no. Why? Because if you look at Joe Kruskal's paper on MST (see here) you don't see anything resembling time complexity. No O(E+Vlog V) or whatnot. So I thought that if the notion of this algorithm runs in such-and-such time was not in the air, then certainly any notion of P could not have been.
Hence I was surprised when I accidentally (more on that later) came across the following:
In 1910 (really, 1910) H.C.Pocklington analyzed two algorithms for solving quadratic congruences and noticed that
one took time proportional to a power of the log of the modulus, where as
the other took time proportional to the modulus itself or its square root.
THAT is the distinction between P and NOT-P.
The paper is titled The determination of the exponent to which a number belongs, the practical solution of certain congruences, and the law of quadratic reciprocity. It appeared in 1910, in the Proceedings of the Cambridge Philosophical Society, Volume 16, pages 1-5. (I could not find it online. If you know of a place online for it, leave a comment.)
How did I come across this? And why had I NOT come across this in my roughly 40 years working in complexity theory?
I came across it while reading a blog of Scotts, The Kolmogorov Option, see here where Pocklington is mentioned in passing. I am surprised how arbitrary the set of things ones knows can be. I have put the Pocklington story in the Demaine-Gasarch-Hajiaghayi book Computational Intractability: A Guide to Algorithmic Lower Bounds so that this knowledge gets to be better known.
ADDED LATER: That Cobham and Edmonds are known for discovering or inventing P is an example of the well known
Columbus Principle: Things are named after the LAST person to discover them (note that Columbus was the last person to discover America.)
Bonus Question: Most principles where the author is not on it, the author might be unknown. NOT in this case. I KNOW who coined the term `Columbus Principle' Do you? (It was not me.)