tag:blogger.com,1999:blog-3722233.post2413030684307587710..comments2020-04-08T16:36:36.701-04:00Comments on Computational Complexity: Knowing some History is a good thing- Why?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger21125tag:blogger.com,1999:blog-3722233.post-46919103960598581802013-04-16T19:34:30.175-04:002013-04-16T19:34:30.175-04:00Context free languages are not closed under inters...Context free languages are not closed under intersection (the wikipedia proof suffices ... consider A={a^n b^n c^m| n,m>=0} and B={a^m b^n c^n| n,m>=0} ... A intersect B = { a^n b^n c^n, n>=0 } which is not c.f. by the pumping lemma.<br /><br />I'm not sure where you got the decidable languages are closed under intersection ... I'm aware of it holding for regular languages ...<br /><br />The citation for the theory in the quotation is (Ginsburg et al., 1967)Anonymoushttps://www.blogger.com/profile/17817548586659422580noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47628994688032184552011-12-16T03:50:27.427-05:002011-12-16T03:50:27.427-05:00Anon 10:19 and CSProf 4:23 are right, i'll jus...Anon 10:19 and CSProf 4:23 are right, i'll just expand upon these:<br />* CFLs can be recognized even in linear space (which is closed under intersection)<br />* let c_1, c_2, ..., c_n be configurations of a TM M; form a word c_1#rev(c_2)#c_3#rev(c_4)#... (where # is a delimiter and rev stands for reverse); we can easily check whether this encodes a computation of M using two (even deterministic) pushdown automata: one will check whether M can get from c_i to c_{i+1} for i odd, the other for i even<br />* corollaries: every r.e. language can be written as h(L1\cap L2) where L1 and L2 are dCFL, h is a homomorphism; the following problems are undecidable: given CFG G,G1,G2, is L(G1)\cap L(G2) empty? is L(G1)=L(G2)? is L(G1) subset of L(G2)? is complement of L(G) empty? is L(G) regular?<br />* btw, this [never heard of stuff] is taught to 2nd grade undergrad students on our universitykukonoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16705499529073990602011-10-03T16:16:41.694-04:002011-10-03T16:16:41.694-04:00Uber techno-nerd Neil Stephenson's latest essa...Uber techno-nerd Neil Stephenson's latest essay for the World Policy Institute, titled <a href="http://www.worldpolicy.org/journal/fall2011/innovation-starvation" rel="nofollow"><i>Innovation Starvation</i></a>, is Stephenson's meditation upon many of the themes of this post.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24037262400602886552011-09-13T09:16:36.426-04:002011-09-13T09:16:36.426-04:00“Knowing some history is a good thing – Why?”
Her...“Knowing some history is a good thing – Why?”<br /><br />Here is hoping that John Sidles’ optimism is justified and that the powers to be can cobble together an economic game plan that avoids a double-dip recession.<br /><br />The current mortgage mess may be a result in part of “lessons not learned” from the Savings and Loan crisis 20 years ago.<br /> <br />The unsettling thing about hedge funds is that they may be operating within the letter of the law and may be natural consequence of economic evolution – bigger (the amount of capital they can leverage), smarter (the algorithms they use for identifying opportunities), and streamlined management that makes them faster and more nimble than their prey -large banks, multi-national corporations and small countries.<br /><br />It may take some forensic accountants teaming up with computer scientists to follow the money and figure out what is really happening.<br /><br />Back to GASARCH’s more specific question:<br /><br />Item 5: “Knowing something about the people can be interesting, but is likely less useful for research and teaching. If you disagree I would love to hear a respectful counterargument.”<br /><br />I think GASARCH may have partially answered his own question in Item 3. <br /><br />Students may benefit from a historic perspective and the views of the minority who challenge difficult and controversial ideas.<br /><br />How many students of theoretical physicists know that Godel and Einstein had an intellectual disagreement over the possibility of a Unified Field Theory?<br /> <br />They were friends at the Institute for Advanced Studies at Princeton in spite of the fact they may have been polar opposites:<br /><br />“Godel was cold and aloof, very serious, and suspicious of common sense. Einstein was warm and affable.” (Hawking’s “God Created the Integers” page 1261)<br /><br />Although Godel did not agree with Einstein’s agenda; in a remarkable display of sheer intellect, Godel wrote a paper that “constructed a rotating model of the universe that satisfied Einstein’s equations”.Jim Blairnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50397451423500387852011-09-12T05:37:02.166-04:002011-09-12T05:37:02.166-04:00While the readers of this blog are tolerant of uno...While the readers of this blog are tolerant of unorthodox spellings, historians are not. If we are to interact with people in the humanities, we have to respect their culture. In the guest post there is a link for "Calender"<br /><br />According to the OED, "calender" is either "one who calenders cloth" (wrings it between two rolling cylinders), or a "member of a mendicant order of dervishes in Turkey and Persia."CSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27941345463815204392011-09-12T05:23:50.304-04:002011-09-12T05:23:50.304-04:00The proof is (by now) standard:
fix a Turing mach...The proof is (by now) standard:<br /><br />fix a Turing machine T that accepts the given r.e. (c.e.!) set<br /><br />intersection of cfls can encode the language L of sequences of instantaneous descriptions of an accepting computation of T on input x [the language L consists of such computations for all x that are accepted]<br /><br />use a homomorphism to erase everything but the input x for each string in LCSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62481848595615984322011-09-10T11:08:19.042-04:002011-09-10T11:08:19.042-04:00Context free languages aren't closed under int...Context free languages aren't closed under intersection so there is no problem with the claim as clarified.<br /><br />Indeed, since a prefix free set (or language if you prefer) can't be a homomorphic image of a non prefix free set the proof will have to go as follow:<br /><br />Create two context free grammars whose resulting languages have an infinite prefix free intersection. Observe that every infinite set is the homomorphic image of an infinite prefix free set. Handle the finite cases by directly stuffing everything into the grammar.Peter Gerdeshttp://invariant.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73537630034496282142011-09-09T13:20:30.093-04:002011-09-09T13:20:30.093-04:00Jim, your post is right-on-the-facts, and yet ther...Jim, your post is right-on-the-facts, and yet there are alternative readings of Umair Haque's essay that (to my mind) are even more interesting and complexity-theoretic.<br /><br />Let's consider the <i>ansatz</i> that trading abuses are not a cause of economic dysfunction, but rather a symptom of dysfunction. What might that dysfunction be?<br /><br />It can't be a shortage of people … the world has plenty. It can't be a shortage of capital … the world has plenty. It can't be a shortage of demand … the world has plenty. <br /><br />So perhaps the world is suffering from an acute shortage of <i>enterprises</i>, that put those people to work … by profitably investing that capital … to meet those demands. <br /><br />Pursuant to this idea, as an exercise in complexity-theoretic enterprise design, I've been colliding NIH Director Francis Collins' recent <i>Reengineering Translational Science: The Time Is Right</i> (2011) with that oldie-but-goodie <i>A Quantum Information Science and Technology Roadmap</i> (QIST/LANL Report/LA-UR-02-6900, 2002). <br /><br />The NIH Roadmap provides outstanding enterprise objectives, the QIST/LANL roadmap (when repurposed in light of subsequent QIT research) provides outstanding enterprise tools … and perhaps these two enterprise roadmaps together have the horsepower to pull us away from the black-hole of economic recession/depression.<br /><br />This merged roadmap is a work-in-progress … perhaps I'll post a summary of it someday. Working out the various STEM details has been fun (and challenging), and for sure, the merged roadmap is a lot more optimistic than Umair Haque's economic scenario of "a burbling event horizon of a massive supergalactic black hole".John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63581273099893418042011-09-09T07:59:37.839-04:002011-09-09T07:59:37.839-04:00This post is in response to John Sidles’ last post...This post is in response to John Sidles’ last post regarding Umair's economic black holes.<br /><br />If I were an economist, I would take a closer look at the black hole effect of hedge funds.<br /><br />A superficial analysis goes something like this:<br /> <br />1. One of the top dogs in the hedge fund world made $5 Billion in 2010. He was also one of the top earners in 2007 at +$3 Billion.(He keeps most of it because he is taxed at 15% rate for capital gains.)<br /><br />2. In 2007 he seems to have made a fortune helping to package and sell junky mortgages and other stuff backed by credit default swaps.<br /><br />3. In 2010, he made a bigger fortune betting against credit default swaps and guessing (with a little help from his friends) that the Federal Government would be forced to acknowledge that AIG was “too big to fail” and then have to pay out on the credit default swaps.<br /><br />4. It doesn’t take a computer scientist (Lance’s tweet 5 days ago) to figure out that the Feds and the taxpayers may have been out gamed by a relatively small cast of “greed is good” characters.Jim Blairnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33652828566202634622011-09-07T14:18:45.533-04:002011-09-07T14:18:45.533-04:00@gasarch: The JACM paper also says "homomorph...@gasarch: The JACM paper also says "homomorphic image" (Theorem 3.1). Let's say the extract you give from IEEE Annals might also be understood as to imply "homomorphic image".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20301588487479490272011-09-07T14:09:58.796-04:002011-09-07T14:09:58.796-04:00GASARCH asks "What of make of all this?"...GASARCH asks "What of make of all this?"<br /><br />We can IT history narrowly as the history of ideas that lead to good <i>theorems</i>, or we can read it broadly as the history of ideas that lead to good <i>enterprises</i> (including theorem-proving). And needless to say, it's neither feasible nor desirable that everyone read IT history the same way.<br /><br />For example, even the most scrupulously pure-minded complexity theorists are sobered by today's global economic climate. As the ardently pro-capitalist economist Umair Haque (who is the Scott Aaronson of 21st century economic theory) writes in this week's HBR blog:<br /><br />----------------------<br /><a href="http://blogs.hbr.org/haque/2011/09/was_marx_right.html" rel="nofollow"><b>Was Marx Right?</b></a><br /><br />“Prosperity as we know is lazily circling the glowing inner rim of the burbling event horizon of a massive supergalactic black hole. And when it comes to doing much about it (wave hello to your new friend, ‘double-dip’), well, the status quo’s pretty much out of options, out of ideas, and running out of time (hey, is that a Congressional “super-committee” being stalked by lobbyists I see? Who came up with this brain-melter of an idea?).”<br /><br />“Wages in many advanced economies — notably, the most purely capitalist in a financialized sense — have failed to keep pace with productivity; not for years, but for decades (America’s median wage has been stagnant for roughly 40 years).”<br />----------------------<br /><br />In the light of IT history, it is natural to ask: Do the theorems of modern complexity theory have <i>any</i> concrete relevance to addressing the problems that Umair's essay identifies?<br /><br />Perhaps one pretty good answer is that <i>some</i> people think so and <i>everyone</i> hopes so. :)John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68007192748941984562011-09-07T12:23:25.305-04:002011-09-07T12:23:25.305-04:00The IEEE Annals of the History of Computer Science...The IEEE Annals of the History of Computer Science,<br />Volume 3, No 1, Jan 1981 <br />has an article by Sheila Greibach entitled<br />Formal Languages: Origins and Directions.<br />Page 32 has the following:<br /><br />What happens if the acceptor is allowed to have multiple storage tapes?<br />One-way nondeterministic acceptors with n tapes, tape i of Scheme i, define<br />precisely the class of homomorphic images of the<br />intersection of n languages. The ith language definable by a realtime<br />acceptor of Scheme i; limitations on the computation time of the acceptor<br />correspond to limitations on the erasing done by the homomorphism<br />(Greibach and Ginsburg 1972; work done in 1968)<br />This generalizes the observation that every recursively enumerable set<br />can be obtained as the intersection of two deterministic CF languages<br />(Ginsberg, Greibach, and Harrison 1966); a corresponding result just<br />for quasi-realtime multipushdown store automata was used to show that<br />NTIME(n) is contained in the family of scattered context languages<br />(Greibach and Hopcroft 1969).<br /><br /><br />Ginsberg, Greibach, Harrison 1966 was a conference paper whose<br />journal version is titled One Way Stack Automata and is in<br />JACM Volume 14, 1967,<br /><br />SO, what to make of all of this?<br />Greibach is incorrect (the intersection of any two CFL's is decidable); <br />however, I think she meant homomorphisms<br />of the intersection of CFL's. The homorphisms can erase,<br />so the image need not be decidable.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9583969916002602852011-09-07T05:50:52.448-04:002011-09-07T05:50:52.448-04:00Anonymous, perhaps systems engineers are prolix by...Anonymous, perhaps systems engineers are prolix by nature. After all, we idealize dynamical processes as being microscopically reversible yet macroscopically irreversible (this includes computation processes) … we view macroscopic processes generically as separations … and about separations there is <a href="http://www.amazon.com/Encyclopedia-Separation-Science-Ten-Set/dp/0122267702" rel="nofollow">much to be said</a> … as every complexity theorist knows. :)John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87006901547342262192011-09-07T04:26:01.982-04:002011-09-07T04:26:01.982-04:00@Anonymous@1:11PM: No it wouldn't: context-fre...@Anonymous@1:11PM: No it wouldn't: context-free languages are closed under homomorphisms.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40976464805031375072011-09-06T22:01:07.738-04:002011-09-06T22:01:07.738-04:00@sidle , u keep on making the same mistakes ... ke...@sidle , u keep on making the same mistakes ... keep ur posts short . oh dear, if I had a wife, and that wife would post on bloggers, then I presume her volume would equate half as much as urs. sigh.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81261682479892343252011-09-06T14:30:27.279-04:002011-09-06T14:30:27.279-04:00I guess this is the usual exercise that checking e...I guess this is the usual exercise that checking emptiness of intersection of two CFLs is undecidable.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44051474827666855322011-09-06T14:11:36.374-04:002011-09-06T14:11:36.374-04:00@anon: Wouldn't it be true that ""An...@anon: Wouldn't it be true that ""Any r.e. set can be written as the homomorphic image of one deterministic context-free language"?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33825675718910982012011-09-06T12:18:51.892-04:002011-09-06T12:18:51.892-04:00About the r.e. representation bit, I don't hav...About the r.e. representation bit, I don't have the issue at hand either, but I'm pretty sure the actual formulation was more like "Any r.e. set can be written as the homomorphic image of the intersection of two deterministic context-free languages."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42536237396103315472011-09-06T11:36:09.008-04:002011-09-06T11:36:09.008-04:00It is well-established that the serious study of h...It is well-established that the serious study of history and mathematics both are historically associated to the advancement of radical agendas. <br /><br />For example, IAS historian Jonathan Israel concludes the Introduction to his just-published <i>Democratic Enlightenment: Philosophy, Revolution, and Human Rights, 1750-1790</i> (Oxford University Press, 2011) with the following quotation from the 18th century polymath Paul-Henri Thiry, Baron d'Holbach:<br /><br />------------<br /><i>“If error and ignorance have forged the chains of peoples, if prejudice perpetuates them, science, reason and truth will one day be able to break them.”</i><br /><br />[Israel concludes …] A noble and beautiful thought, no doubt, but was he [d'Holbach] right? That was and remains today the unresolved challenge of the Radical Enlightenment.<br />------------<br /><br />Following-up Prof. Israel's question, we are led naturally to ask, to what extent do modern-day weblogs like <i>Computational Complexity</i>, <i>Gödel's Lost Letter</i>, <i>Shtetl Optimized</i>, <i>Combinatorics and More</i>, and <i>The Opinions of Doron Zeilberger</i> (plus the newly reborn <i>Quantum Pontiff</i> and many more) all serve to advance — whether deliberately or unwittingly — the various technologically and socially radical objectives of humanity's ongoing Enlightenment?<br /><br />The answer varies obviously with the individual readers of these weblogs, and (to express my own opinion) when read with an eye to systems engineering objectives and enterprises … well … modern computational complexity theory is a white-hot nexus of transformational ideas and tools that already are greatly accelerating the 21st century's d'Holbach-style enterprises … and promise further, still greater accelerations in decades to come. <br /><br />For which, appreciation and thanks are extended to Lance and GASARCH … and to Jeffrey Stein for encouraging us all to appreciate the radical historical context that is ancestral to all of today's radical mathematical advances. :)John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11187038954814760992011-09-06T11:34:09.572-04:002011-09-06T11:34:09.572-04:00AH- you are correct. I will double check what is s...AH- you are correct. I will double check what is says;<br />however, my issue is at home.<br />IEEE Annals of the History of Computer Science, 1981,<br />Volume 3 has an issue devoted to theory. <br /><br />I could not find it on line but if someone else does please check what she wrote.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76044955429036290792011-09-06T11:19:41.846-04:002011-09-06T11:19:41.846-04:00"any r.e. set can be written as the intersect..."any r.e. set can be written as the intersection of two context free languages"<br /><br />What am I missing here? Every context-free language is decidable. The decidable languages are closed under intersection. So the intersection of any two context-free languages is decidable. Therefore any undecidable r.e. language is not the intersection of two context-free languages.Anonymousnoreply@blogger.com