tag:blogger.com,1999:blog-3722233.post2374034479146058976..comments2024-06-24T15:24:01.378-05:00Comments on Computational Complexity: Who first thought of the notion of Polynomial Time? Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-3722233.post-258403164334381722024-04-25T18:36:38.892-05:002024-04-25T18:36:38.892-05:00In the Symposium on the Theory of Graphs and its A...In the Symposium on the Theory of Graphs and its Applications held in Smolenice (Czechoslovakia) in June 1963, the Soviet graph theorist A. A. Zykov (then based at Novosibirsk) posed the problem of whether the Tutte polynomial of a graph --- or even its chromatic polynomial --- can be computed by a method that improves on brute force in the same way in which efficient methods for computing the determinant (e.g., Gaussian elimination) improve on direct calculation from the definition (as a sum over permutations of the row/column index set). This is in:<br /> A. A. Zykov, Problem 31, in<br /> Theory of Graphs and its Applications<br /> (Proc. Sympos. Smolenice, 1963),<br /> Publ. House Czechoslovak Acad. Sci., Prague, 1964, p. 165.<br /><br />In his statement of this problem, Zykov didn't formulate a definition of polynomial time, and the problem is somewhat informal, but he did seem to be intuitively aware of the essential difference in character between polynomial- and exponential-time algorithms, and his problem expresses that difference in a way that his audience could immediately relate to.<br /><br />He actually poses the question more generally, for representable matroids (though he does not use that term) given by an appropriate matrix representation, rather than just graphs.<br /><br />He frames his question in terms of the coefficient array for the Whitney rank generating function rather than the Tutte polynomial. But it amounts to the same thing: the Whitney rank generating function and the Tutte polynomial differ only by a coordinate translation of 1 in each direction. His question about the chromatic polynomial is again framed in terms of its coefficients.<br /><br />I discuss this briefly in section 12 of:<br /> G Farr, The history of Tutte–Whitney polynomials, in:<br /> J A Ellis-Monaghan and I Moffatt,<br /> Handbook of the Tutte Polynomial and Related Topics,<br /> Chapman and Hall/CRC, 2022, Chapter 34, pp. 623--668.Graham Farrhttps://users.monash.edu/~gfarr/noreply@blogger.comtag: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