http://blog.computationalcomplexity.org/2022/11/who-first-thought-of-notion-of.html Computational Complexity Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch Google Analytics Monday, November 14, 2022 Who first thought of the notion of Polynomial Time? (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.) ADDED LATER: Here is the article in pieces: Page 1, Pages2,3, Pages4,5. 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.) Posted by gasarch at 10:18 PM # # Email ThisBlogThis!Share to TwitterShare to FacebookShare to Pinterest 9 comments: 1. [blank] Evangelos Georgiadis3:54 AM, November 15, 2022 Scott is referring to a slightly different paper, mentioning 1917 as publication date. Note that Don Knuth in TAOCP Vol 2 has an exercise under Factorization of Polynomials (section 4.6.2); see Exercise 15 (Square Roots Modulo a Prime): Design an algorithm to calculate the square root of a given integer $u$ modulo a given prime $p$. He mentions the paper that Scott is referring to (i.e., H. C. Pocklington, Proc. Camb. Phil. Soc. 19 (1917), p.57--59). I think that even Don only became aware of the Pocklington phenomenon later on ... in 1996 ... but that needs double checking. NB: There's another exercise in section 4.5.4, suggested by H.C. Pocklington in 1914 (!), but this is related to Factoring Primes. ReplyDelete Replies Reply 2. [ava] Tuncay8:43 AM, November 16, 2022 Didn't Kurt Godel 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. ReplyDelete Replies 1. [blogger_lo] gasarch9:19 AM, November 16, 2022 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. Delete Replies Reply Reply 3. [blank] Anonymous8:48 AM, November 16, 2022 Literally no one gives a shit ReplyDelete Replies Reply 4. [blank] Juan8:55 AM, November 16, 2022 Cool findings! I mention Pocklington paper in my lectures. Nitpick about "Columbus principle" is a counterexample to itself. 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. A correction would be "Things are named BY the last person to discover them", but that doesn't take into account rediscoveries. A better principle would "Things are named by the person who popularizes it the most". 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". I propose to rename "Columbus principle" to "Nothing should be named after Columbus except Columbus principle" ReplyDelete Replies 1. [blogger_lo] gasarch9:12 AM, November 16, 2022 AH, I should have said Credit is given to the last person to discover something. Columbus is given credit for discovering America. And yes, life is more complicated than that. It would be interesting to study how things get their name. Delete Replies Reply Reply 5. [blank] Martin Berger10:43 AM, November 16, 2022 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_efficiency ReplyDelete Replies 1. [blogger_lo] gasarch3:23 PM, November 16, 2022 Great- Yes- very relevant! If my book was not already over 540 pages I might include that (I might anyway). More generally, a history of awarness of computational issues and how formal they are could be... another whole book! Delete Replies Reply Reply 6. [blank] Jochen L. Leidner1:30 PM, November 16, 2022 > I've heard rumors that IBM had search engines way before Google but could not figure out how to make money off of it. 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. ReplyDelete Replies Reply Add comment Load more... Older Post Home Subscribe to: Post Comments (Atom) Books [k9937] Commissions earned from Amazon Links Tweets by fortnow Blog Links * Bill's Home Page * Lance's Home Page * Videos * Podcasts * Posts Feed * Comments Feed * Foundations of Complexity Lessons * The Golden Ticket * Computational Intractability: A Guide to Algorithmic Lower Bounds * P v NP Survey (2009) * Fifty Years of P vs. NP (2022) * CACM Conference Viewpoint * Favorite Theorems * Favorite Complexity Books (commissions earned) * Graduate Student Guide * Bublup Rollup on P v NP Popular Posts * Who first thought of the notion of Polynomial Time? * 2019 Fall Jobs Post * What was the recent Nobel Prize in Physics really about?(Guest Post) * 2020 Fall Jobs Post * Alpha Tensor * Why did 1+1=2 take Russell and Whitehead 300 pages? * Should you quit Twitter and Texas? * Euclidean TSP is NP-hard but not known to be in NP. Why not known? * The Structure of Data and Machine Learning * The Media Coverage of the Matrix result is Terrible (though not worse than usual) Complexity Links * Complexity Conference * SIGACT * Theory Announcements * Theory Stack Exchange * Complexity Zoo * Complexity on arXiv * Electronic Colloquium on Computational Complexity Blog Archive * V 2022 (67) + V November (4) o Who first thought of the notion of Polynomial Time? o The Structure of Data and Machine Learning o Euclidean TSP is NP-hard but not known to be in NP... o Should you quit Twitter and Texas? + > October (9) + > September (6) + > August (7) + > July (6) + > June (5) + > May (6) + > April (5) + > March (6) + > February (7) + > January (6) * > 2021 (89) + > December (6) + > November (7) + > October (8) + > September (8) + > August (9) + > July (7) + > June (7) + > May (8) + > April (8) + > March (7) + > February (6) + > January (8) * > 2020 (76) + > December (8) + > November (7) + > October (7) + > September (7) + > August (6) + > July (6) + > June (6) + > May (7) + > April (7) + > March (9) + > February (1) + > January (5) * > 2019 (84) + > December (4) + > November (3) + > October (8) + > September (7) + > August (2) + > July (8) + > June (9) + > May (9) + > April (9) + > March (8) + > February (8) + > January (9) * > 2018 (100) + > December (7) + > November (8) + > October (10) + > September (8) + > August (9) + > July (8) + > June (8) + > May (9) + > April (9) + > March (8) + > February (8) + > January (8) * > 2017 (102) + > December (7) + > November (8) + > October (9) + > September (8) + > August (9) + > July (9) + > June (9) + > May (9) + > April (9) + > March (8) + > February (8) + > January (9) * > 2016 (102) + > December (9) + > November (8) + > October (9) + > September (7) + > August (8) + > July (7) + > June (10) + > May (9) + > April (10) + > March (8) + > February (9) + > January (8) * > 2015 (103) + > December (7) + > November (9) + > October (9) + > September (8) + > August (9) + > July (9) + > June (10) + > May (8) + > April (9) + > March (9) + > February (8) + > January (8) * > 2014 (111) + > December (8) + > November (8) + > October (10) + > September (11) + > August (9) + > July (9) + > June (11) + > May (10) + > April (10) + > March (8) + > February (8) + > January (9) * > 2013 (108) + > December (9) + > November (8) + > October (8) + > September (11) + > August (9) + > July (9) + > June (8) + > May (9) + > April (10) + > March (9) + > February (9) + > January (9) * > 2012 (132) + > December (7) + > November (9) + > October (12) + > September (10) + > August (10) + > July (9) + > June (10) + > May (12) + > April (12) + > March (15) + > February (14) + > January (12) * > 2011 (134) + > December (10) + > November (10) + > October (12) + > September (13) + > August (10) + > July (10) + > June (14) + > May (11) + > April (12) + > March (12) + > February (11) + > January (9) * > 2010 (191) + > December (8) + > November (12) + > October (15) + > September (14) + > August (18) + > July (15) + > June (17) + > May (20) + > April (22) + > March (20) + > February (15) + > January (15) * > 2009 (249) + > December (16) + > November (19) + > October (23) + > September (21) + > August (21) + > July (23) + > June (23) + > May (22) + > April (21) + > March (22) + > February (20) + > January (18) * > 2008 (253) + > December (19) + > November (18) + > October (27) + > September (21) + > August (19) + > July (22) + > June (23) + > May (23) + > April (22) + > March (20) + > February (21) + > January (18) * > 2007 (159) + > December (10) + > November (15) + > October (18) + > September (10) + > August (13) + > July (11) + > June (8) + > May (8) + > April (7) + > March (16) + > February (20) + > January (23) * > 2006 (238) + > December (18) + > November (22) + > October (22) + > September (19) + > August (24) + > July (18) + > June (18) + > May (18) + > April (18) + > March (21) + > February (20) + > January (20) * > 2005 (237) + > December (18) + > November (20) + > October (24) + > September (19) + > August (22) + > July (17) + > June (19) + > May (21) + > April (19) + > March (17) + > February (17) + > January (24) * > 2004 (200) + > December (18) + > November (16) + > October (19) + > September (15) + > August (16) + > July (15) + > June (18) + > May (13) + > April (13) + > March (17) + > February (16) + > January (24) * > 2003 (149) + > December (13) + > November (12) + > October (15) + > September (11) + > August (7) + > July (11) + > June (13) + > May (10) + > April (15) + > March (15) + > February (11) + > January (16) * > 2002 (76) + > December (20) + > November (17) + > October (15) + > September (18) + > August (6) Blog Roll * Godel's Lost Letter and P=NP The Gerrymanders Have It 7 hours ago * Combinatorics and more Barnabas Janzer: Rotation inside convex Kakeya sets 9 hours ago * 11011110 Linkage 1 day ago * Shtetl-Optimized Sam Bankman-Fried and the geometry of conscience 3 days ago * Process Algebra Diary Two faculty positions in Computer Science at Reykjavik University 4 days ago * FYI: The AIP Bulletin of Science Policy News Psyche Delay Compels JPL to Reckon With Overstretched Staff 5 days ago * What's new UCLA Math Undergraduate Merit Scholarship for 2023 1 week ago * Bits and Pieces Harvard Alumni: Sign Harvey Silverglate's petition to get on the ballot for the Overseers 1 week ago * Windows On Theory Postdocs at Harvard! 2 weeks ago * Theory Matters ACM survey on math requirements for the CS major 2 weeks ago * Thoughts Correlation bounds against polynomials, a survey 4 weeks ago * Mathematical Enchantments Teaching with Magic Paper 4 weeks ago * GovAffairs U.S. Must Follow Through on NSF Funding or Risk Falling Behind Competitors, Says Former CRA Board Chair 4 weeks ago * Healthy Algorithms Three cheers for pdb 3 months ago * Off the convex path Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Networks 4 months ago * in theory Workshop on Fairness in AI 4 months ago * Kamathematics Guest post: COLT 2022 Call for Open Problems 4 months ago * The Big Data Theory Theory Jobs 2022 5 months ago * My Brain is Open Crypto Newsletter 5 months ago * Announcing an automatic theorem proving project - Gowers's Weblog Announcing an automatic theorem proving project 6 months ago * Turing's Invisible Hand CFP: SCW Special Issue on "Fair Public Decision Making" 8 months ago * My Biased Coin Postdoc call for FODSI 1 year ago * Opinions of Doron Zeilberger Show 10 Show All Creative Commons License Computational Complexity Weblog by Lance Fortnow and William Gasarch is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Additional permissions can be requested. Awesome Inc. theme. Powered by Blogger.