tag:blogger.com,1999:blog-3722233.post2374034479146058976..comments2023-12-01T22:15:08.991-06:00Comments on Computational Complexity: Who first thought of the notion of Polynomial Time? Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-3722233.post-89640850951469831842022-11-27T17:53:11.435-06:002022-11-27T17:53:11.435-06:00In addition to Cobham and Edmonds, the third near-...In addition to Cobham and Edmonds, the third near-simultaneous (?) "introduction" of P that I knew of was: Rabin, "Mathematical Theory of Automata" (Proc. Symp. Appl. Math. of the AMS, Vol. 19, 1967), see pp. 159-160; the symposium was held in 1966. Although technically (shortly) after Cobham and Edmonds, he does not cite them - I do not know if he was aware of them, but he makes no mention of it. I had always thought of the three (Cobham, Edmonds, Rabin) as near-simultaneous independent introductions of the same concept.<br /><br />Also, my impression is that Cobham : Edmonds / Rabin. :: Church : Turing. In the sense that Cobham introduced a definition of P but made no real argument for it, whereas Edmonds and Rabin both did. (Similarly, Church introduced lambda calculus, but Turing was the one who really made a cogent argument that Turing machines actually captured what we intuitively meant by "computation")Joshua A. Grochowhttps://home.cs.colorado.edu/~jgrochow/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91680574278649974912022-11-21T01:34:00.499-06:002022-11-21T01:34:00.499-06:00FWIW, I think I learned about H. C. Pocklington fr...FWIW, I think I learned about H. C. Pocklington from Jeff Shallit.<br /><br />Regarding IBM anticipating Google, maybe you're thinking of the CLEVER project, which Jon Kleinberg led while at IBM Almaden around 1996? It was roughly contemporaneous with Brin and Page's PageRank.Scotthttps://www.blogger.com/profile/13456161078489400740noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30648507403525143222022-11-18T21:48:00.850-06:002022-11-18T21:48:00.850-06:00From https://en.wikipedia.org/wiki/Euclidean_algor...From https://en.wikipedia.org/wiki/Euclidean_algorithm: "A more efficient version of the algorithm .... was proven by Gabriel Lamé in 1844, and marks the beginning of computational complexity theory. "Yuval Pereshttps://yuvalperes.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39600173362607134232022-11-17T13:50:11.895-06:002022-11-17T13:50:11.895-06:00Hi, for von Neumann the article [0] claims some no...Hi, for von Neumann the article [0] claims some notions of computational complexity from a paper of his in 1953. I would also add on page 28 of [1] Gregory Chaitin claims that he first heard ideas about computational complexity from von Neumann some time around 1950, so perhaps giving him an email about this might give you a bit of history.<br /><br />[0]: https://www.redalyc.org/articulo.oa?id=265219625004<br />[1]: https://link.springer.com/book/10.1007/978-1-4471-0185-7Jonathannoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75666973724682562162022-11-16T15:23:01.608-06:002022-11-16T15:23:01.608-06:00Great- Yes- very relevant! If my book was not alr...Great- Yes- very relevant! If my book was not already over 540 pages I might include that (I might anyway). <br /><br />More generally, a history of awarness of computational issues and how formal they are could be... another whole book!gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32229008699729644232022-11-16T13:30:16.242-06:002022-11-16T13:30:16.242-06:00> I've heard rumors that IBM had search eng...> I've heard rumors that IBM had search engines way before Google but could not figure out how to make money off of it.<br /><br />You might be referring to IBM's early Text Analytics platform WebFountain here (Gruhl et al. 2004, IBM Sys. J.), which contained aspects from a search engine, but I wouldn't say it qualifies to be called a Web search engine. Before Google, there notably was AltaVista, though.Jochen L. Leidnerhttp://jochenleidner.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27922825506866093582022-11-16T10:43:44.381-06:002022-11-16T10:43:44.381-06:00I don't know to what extent this is relevant, ...I don't know to what extent this is relevant, but the computational complexity of the Euclidean algorithm for GCD has been studied since the 19th century. See https://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiencyMartin Bergerhttps://martinfriedrichberger.net/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35963707028985218622022-11-16T09:19:10.636-06:002022-11-16T09:19:10.636-06:00Your are referring to Godel's lost letter. A g...Your are referring to Godel's lost letter. A good article about this is Von Neumann, Godel and Complexity Theory, by Urquhart, in Bull of Symbolic Logic, Vol 16, No 4, 516--530. And YES there wer SOME notions of time complexity in the air between Pocklington and Cobham/Edmonds. but not much. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57597126975047127852022-11-16T09:12:57.251-06:002022-11-16T09:12:57.251-06:00AH, I should have said
Credit is given to the las...AH, I should have said<br /><br />Credit is given to the last person to discover something.<br /><br />Columbus is given credit for discovering America. <br /><br />And yes, life is more complicated than that. It would be interesting to study how things get their name.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81432440647931712622022-11-16T08:55:55.258-06:002022-11-16T08:55:55.258-06:00Cool findings! I mention Pocklington paper in my l...Cool findings! I mention Pocklington paper in my lectures.<br /><br />Nitpick about "Columbus principle" is a counterexample to itself. <br />1) America is not named after him 2) "Things are named AFTER the last person to discover them" I highly doubt that he discover that principle at all.<br /><br />A correction would be "Things are named BY the last person to discover them", but that doesn't take into account rediscoveries.<br /><br />A better principle would "Things are named by the person who popularizes it the most".<br /><br />But then, we can take into account that things can have many names and we get "things have many names, the popularity of a name is usually proportional to the popularity of the people using that name".<br /><br />I propose to rename "Columbus principle" to "Nothing should be named after Columbus except Columbus principle"Juanhttps://juan.com.uynoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2570240031158687012022-11-16T08:48:44.544-06:002022-11-16T08:48:44.544-06:00Literally no one gives a shitLiterally no one gives a shitAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4084783260926078712022-11-16T08:43:30.656-06:002022-11-16T08:43:30.656-06:00Didn't Kurt Gödel consider quadratic time to b...Didn't Kurt Gödel consider quadratic time to be a sort of upper limit of feasibility in a letter to von Neumann in the 50s? Certainly not all of P directly, but a notion that a constant degree of n qualifies somewhat as a major precursor.Tuncayhttps://www.blogger.com/profile/10454317715585232437noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10070834884053639332022-11-15T03:54:04.260-06:002022-11-15T03:54:04.260-06:00Scott is referring to a slightly different paper, ...Scott is referring to a slightly different paper, mentioning 1917 as publication date.<br /><br />Note that Don Knuth in TAOCP Vol 2 has an exercise under <br />Factorization of Polynomials (section 4.6.2); see Exercise 15 <br />(Square Roots Modulo a Prime): Design an algorithm to calculate the square root of a given integer $u$ modulo a given prime $p$. <br />He mentions the paper that Scott is referring to <br />(i.e., H. C. Pocklington, Proc. Camb. Phil. Soc. 19 (1917), p.57--59).<br /><br />I think that even Don only became aware of the Pocklington phenomenon later on ... in 1996 ... but that needs double checking.<br /><br />NB: There's another exercise in section 4.5.4, suggested by H.C. Pocklington in 1914 (!), but this is related to Factoring Primes.Evangelos Georgiadisnoreply@blogger.com