tag:blogger.com,1999:blog-3722233.post5085507759987895671..comments2024-08-02T19:37:12.269-05:00Comments on Computational Complexity: Quantum Leap/Quantum of Solace/What does Quantum mean anyway?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-41058115865610569172008-12-11T17:53:00.000-06:002008-12-11T17:53:00.000-06:00The working title of the latest Bond film was "Mod...The working title of the latest Bond film was "Modicum of Respite"<BR/>(stolen from Connan O'Brien, Harvard '8<BR/><BR/>--Mom of PhD hopefulAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83171939660359274492008-12-04T08:56:00.000-06:002008-12-04T08:56:00.000-06:00How about a Cauchy like definition of continuity? ...How about a Cauchy like definition of continuity? <BR/><BR/>A function is Gasarch continuous if <BR/><BR/>(a) it is uniformly continuous or <BR/><BR/>(b) |x-y| < delta implies |f(x)-f(y)| < epsilon*c(x), where c(x) is a Gasarch continuous function.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69661793479932109772008-12-04T08:38:00.000-06:002008-12-04T08:38:00.000-06:00Our intuition of what is a continuous function is ...Our intuition of what is a continuous function is fuzzy. Say consider the function x^(1/3). Is it continuous around zero? <BR/><BR/>In some sense yes, as we can "draw it without lifting the pencil". In another sense no, as the value of the function changes very rapidly around zero.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64735170029608021812008-12-04T07:37:00.000-06:002008-12-04T07:37:00.000-06:00The term uniformily continuos takes care of this, ...<I>The term uniformily continuos takes care of this, but they should just rename things so math-continuos matches common-sense-continuos.</I><BR/><BR/>The function f(x)=x^2 (defined on R) is common-sense-continuous and math-continuous; but it is not uniformly-continuous.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27131018851220764602008-12-03T20:15:00.000-06:002008-12-03T20:15:00.000-06:00Bill, if you worked in algorithms rather than comp...Bill, if you worked in algorithms rather than complexity, you may have encountered the word parsimonious earlier. An important paper in the field of network design is:<BR/><BR/>M.X. Goemans and D. Bertsimas, Survivable Networks, Linear Programming Relaxations and the Parsimonious Property, Mathematical Programming, 60, 145--166, 1993.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2555605317827147692008-12-03T19:52:00.000-06:002008-12-03T19:52:00.000-06:00The notion of parsimony as a positive attribute go...The notion of parsimony as a positive attribute goes at least back to Occam's Razor which is also known in Latin as "lex parsimoniae".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27272260226728064702008-12-03T19:47:00.000-06:002008-12-03T19:47:00.000-06:00The word continuos as it is used in math bothers m...<I>The word continuos as it is used in math bothers me. There are some functions that look non-continuos but by the formal definition they are. The term uniformily continuos takes care of this, but they should just rename things so math-continuos matches common-sense-continuos.</I><BR/><BR/>In mathematics it is important to have a definition that captures that are mathematically important. The motivation for definitions should be primarily about how they fit with the mathematics. E.g. "compact" is a very useful definition not because it captures the original meaning of compact, but because it captures exactly the properties you care about for many things.<BR/><BR/><BR/><BR/><I>However American dictionaries tend to equate parsimonious with stingy and all its negative connotations.</I><BR/><BR/>I missed the word "dictionary" the first time I read this. Twas an amusing misreading.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10690598174927958842008-12-03T16:53:00.000-06:002008-12-03T16:53:00.000-06:00If a physical or informatic quantity is invariant ...If a physical or informatic quantity is invariant under Mike and Ike's Theorem 8.3 "Unitary freedom in the operator-sum representation", then it is (by my working definition) quantum.<BR/><BR/>Otherwise, not. <BR/><BR/>This definition encompasses all of scattering theory, for example ... which according to the Feynman-Wheeler motto "everything as scattering" means it encompasses all of physics. <BR/><BR/>And further, it encompasses a great range of topics in information theory, complexity theory, and simulation science too.<BR/><BR/>That's my working definition of "quantum", anyway ... its main virtue is it is mathematically well-posed!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62686890243269064342008-12-03T14:21:00.000-06:002008-12-03T14:21:00.000-06:00The OED agrees with Bill. Parsimonious means effic...The OED agrees with Bill. Parsimonious means efficient, economic: "Her expenditure was parsimonious and even miserly".<BR/><BR/>However American dictionaries tend to equate parsimonious with stingy and all its negative connotations.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17523605590844834462008-12-03T14:20:00.000-06:002008-12-03T14:20:00.000-06:00Williams Safire has a column in the New York Times...Williams Safire has a column in the New York Times ("On Language" in the Sunday NYT magazine) about 10 years ago. His conclusion was that it sometimes takes on both meanings of "big" and "small".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59929586683481820812008-12-03T13:21:00.000-06:002008-12-03T13:21:00.000-06:00Before Planck et al, "quantum" was a Latin word, a...Before Planck et al, "quantum" was a Latin word, a form of "quantus", which just means quantity. It carries a natural connotation of indivisibility even if doesn't explicitly mean that. Since it is standard Latin and close to the English word "quantity", it may have been used in English before then, although a cursory search in Google Books suggests it mainly appeared in the phrase "quantum meruit", which literally translates as "deserved quantity" and means "reasonable compensation for an incomplete contract". That meaning does not imply discreteness.<BR/><BR/>Now that quantum mechanics is entrenched, "quantum" usually means an indivisible quantity of something measured continuously.<BR/><BR/>If they had been fans of English rather than Latin, they might have used a word like "lump". (After all, "lump sum equivalent" is very similar to "quantum meruit".) Then we would be studying "lump mechanics" instead of quantum mechanics.Greg Kuperberghttps://www.blogger.com/profile/16655664043505766628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80281333722732899012008-12-03T12:15:00.000-06:002008-12-03T12:15:00.000-06:00The word continuos as it is used in math bothers m...<I>The word continuos as it is used in math bothers me.</I><BR/><BR/>It bothers me too, to the extent it is used at all. :-)<BR/><BR/><I>There are some functions that look non-continuos but by the formal definition they are. The term uniformily continuos takes care of this, but they should just rename things so math-continuos matches common-sense-continuos.</I><BR/><BR/>That's 100% backwards. Instead, your common-sense intuition should be revised to fit the definitions. I'm actually serious about this: intuition needs to be built and extended, and there's nothing sacred about whatever intuitions you start the process with.<BR/><BR/>As for this specific issue, I don't even think common sense agrees with you. Common sense suggests that continuity should be a local property; by contrast, uniform continuity is intrinsically global.<BR/><BR/><I>I don't quite see why thats really what you want to call these reductions.</I><BR/><BR/>It was probably inspired by the use of the term "parsimony" in biology to mean efficiency in the Occam's Razor sense.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1820838108247857872008-12-03T11:32:00.000-06:002008-12-03T11:32:00.000-06:00According to the OED "quantum" was already used in...According to the OED "quantum" was already used in 1564 with the philosophical meaning "something that has quantity". (The example that it gives is John Jewel's "that ye body of Christ is quantum in Eucharistia".) So, yes, that predates even classical mechanics.Wim van Damhttps://www.blogger.com/profile/14484831637730978511noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89545490733735972732008-12-03T11:29:00.000-06:002008-12-03T11:29:00.000-06:00This comment has been removed by the author.Wim van Damhttps://www.blogger.com/profile/14484831637730978511noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60134471785586213532008-12-03T11:28:00.000-06:002008-12-03T11:28:00.000-06:00My sense of the ex-science definition of quantum a...My sense of the ex-science definition of quantum agrees with what Matt said. A quantum is 1 of whatever unit is used to measure something, e.g. 1 head of cattle, 1 share of stock, 1 barrel of oil...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85015296510766851392008-12-03T11:21:00.000-06:002008-12-03T11:21:00.000-06:00According to the wiktionary quantum originally jus...According to the wiktionary quantum originally just meant quantity or amount, with no implication of discreteness, largeness or smallness.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59080116787980227722008-12-03T11:17:00.000-06:002008-12-03T11:17:00.000-06:00It means thrifty but with a positive angle (as opp...<I>It means thrifty but with a positive angle (as opposed to cheap).</I><BR/><BR/>This is not correct, in my experience, and according to the dictionary I just checked. ("Ungenerously or pettily reluctant to spend money") It in fact does mean cheap in the sense you allude to.<BR/><BR/>Just making sure our young complexity theorists can appreciate the joke for one moment in their lives...Anonymousnoreply@blogger.com