tag:blogger.com,1999:blog-3722233.post1856547382949615282..comments2024-03-29T08:55:55.727-05:00Comments on Computational Complexity: Are there any longstanding conjectures that ended up being false?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger22125tag:blogger.com,1999:blog-3722233.post-32176521109300619732010-07-27T17:14:59.073-05:002010-07-27T17:14:59.073-05:00...we must know, we will know!...we must know, we will know!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71287578163011449432010-06-22T22:51:44.128-05:002010-06-22T22:51:44.128-05:00While Cooper announced a sketch of the proof of th...While Cooper announced a sketch of the proof of the definability of the jump there were some holes that weren't filled in really satisfactorily until Slaman and Shore's proof.<br /><br />To my knowledge the existence of a nontrivial automorphism of the Turing degrees is still regarded as an open question with the best widely accepted result last time I looked being (by Slaman and Woodin I believe) that any such automorphism must be the identity above...0'' I believe. I think Cooper made a significant advance (showing it had to be the identity above 0'''??) but didn't settle the whole question. He may have claimed the existence of an automorphism but until there is a detailed proof it's not really settled.<br /><br />In any case while people surely had intuitions one way or another about these problems they never rose to the level of 'the community would be stunned if the Turing degrees weren't rigid'Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40928333393705436742009-06-13T12:36:06.420-05:002009-06-13T12:36:06.420-05:00Maybe not "dramatic" (but at least as dr...Maybe not "dramatic" (but at least as dramatic as some of the other examples here).<br /><br /><a href="http://www.maths.leeds.ac.uk/~pmt6sbc/" rel="nofollow">Barry Cooper</a> is a recursion-theorist from Leeds University who has solved not one but at least two relevant, long-standing conjectures related to the semilattice of Turing degrees. In both cases, in the surprising direction.<br /><br />One was already asked by Post, if I remember correctly: prove that the first-order theory of the comparison of the Turing degrees is insufficient to define the jump; of course, anyone can "see" that if your expression language is just the T-reduction you cannot speak about halting machines. However, Barry proved in the late 80's that it IS possible to define the jump in such a limited language. <br /><br />Also, it was widely expected that the semilattice of the Turing degrees was rigid; but Barry found in the mid or late 90's a nontrivial automorphism.<br /><br />(I would welcome that someone more knowledgeable confirms or corrects my descriptions.)<br /><br /><i>José L Balcázar</i>Balquihttps://www.blogger.com/profile/09857844891905542749noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45923819175366026972009-06-11T09:06:33.740-05:002009-06-11T09:06:33.740-05:00A very good and thoroughly documented example of &...A very good and thoroughly documented example of "a longstanding conjecture that ended up being false" can be found on the American Institute of Physics' web site on global warming:<br /><br />http://www.aip.org/history/climate/co2.htm<br /><br />The conjecture was an important one: <i>Anthropogenic increases in CO2 concentration exert minimal effect on Earth's climate.</i> <br /><br />The evidence was (too-simple) radiation transport experiments supported by (too-simple) mathematical models. The AIP web site thoroughly documents these errors.<br /><br />The error was embraced by the the scientific community (roughly) from Knut Ångström's CO2 absorption experiments of 1900, to Lewis Kaplan layer-based modeling of 1952. <br /><br />It is interesting that these errors are still publicly embraced today, mainly by ideology-driven far-right web sites, and also by organizations funded by the carbon industry.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60702699507836615222009-06-10T01:19:51.373-05:002009-06-10T01:19:51.373-05:00Such a dramatic result was last year's counter...Such a dramatic result was last year's counterexample [Nature Physics, March 09] by Hastings showing that "the additivity conjectures" from quantum information theory were all false. A huge community of people, including operator theorists, physicists, information theorists and computer scientists, had been working on the problem. However,his counterexamples were by random selection and led to very tiny violations of additivity for extremely large channels and important questions still remain. How big can the violations be? Can a general formula for the classical capacity of quantum channels be given? Is the classical capacity itself additive? <br /><br />An analogous questions to the latter about quantum channels was shown to be false a few months before Hastings's counterexample appeared, when the quantum capacity was shown to not be additive by Smith and Yard [Science, Sept. 08]. Some time later, nonadditivity of the private capacity was then demonstrated by Li, Winter, Zou and Guo. <br /><br />Of the above, the work by Hastings was the most high-profile, since the greatest number of people had been working on / were aware of the problem. The community seemed largely split on it, in part because Hastings completed a program initiated by Hayden and Winter to provide counterexamples. Their approach came close to generating counterexamples, but fell short, which some saw as a sign that additivity was "trying" really hard to be true, while others (correctly) believed that their methods just needed strengthening (as Hastings did).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32692275360773766872009-06-09T23:21:43.426-05:002009-06-09T23:21:43.426-05:00Just for the record, what is the status of the uni...Just for the record, what is the status of the unique games conjecture? Is it currently widely-believed to be true? False? no general agreement?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80648419266328261602009-06-09T15:33:52.743-05:002009-06-09T15:33:52.743-05:00The adjacency of GASARCH's post about widely e...The adjacency of GASARCH's post about widely embraced conjectures, with Lance's post about taking his daughter miniature golfing, points out one more widely embraced conjecture that perhaps many parents contemplate: "Our shared global civilization and planetary ecology will endure."<br /><br />Carlton Caves' preprint (http://arxiv.org/abs/0806.3538v1) gives a readable summary of the purely probabilistic arguments for this conjecture, both pro and con. <br /><br />From a historical point of view, I think many readers of this column will be familiar with Jared Diamond's writings on this conjecture.<br /><br />Obviously, this particular conjecture is not likely to be resolved by reasoning from mathematical axioms ... still it undeniably has a very substantial mathematical component.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60893550521721830292009-06-09T14:48:01.550-05:002009-06-09T14:48:01.550-05:00There plenty of examples in which practical engine...There plenty of examples in which practical engineering problems proved considerably easier than the consensus option. <br /><br />Fast algorithms for discrete Fourier transforms came as a surprise to many, as did Dantzig's simplex algorithm. <br /><br />In recent years, compressive sampling methods have confounded conventional wisdom ... this story is well-told in essays by Candes and Tao, and by Donoho, in the December 2008 IEEE Information Theory Society Newsletter.<br /><br />Emerging surprises: classical methods for simulating large-scale quantum system dynamics already perform much better than (say) Feynman's generation foresaw, and the pace of improvement is itself accelerating.<br /><br />Future surprises: efficient integer factoring would surprise many people, but by no means everyone.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61663443934965608312009-06-09T12:07:19.093-05:002009-06-09T12:07:19.093-05:00Oh! here is a famous one in model theory:
Hrushovs...Oh! here is a famous one in model theory:<br />Hrushovski's construction refuting Lachlan and Zilber's conjectures.<br /><br />http://en.wikipedia.org/wiki/Hrushovski_constructionAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59809318496741203492009-06-09T12:01:59.396-05:002009-06-09T12:01:59.396-05:00Was it explicitely conjectured
that IP does not co...Was it explicitely conjectured<br />that IP does not contain co-NP<br />(and higher classes)? It was<br />definitely surprising.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30304799006586102942009-06-09T06:19:18.793-05:002009-06-09T06:19:18.793-05:00Does Barrington's theorem about 5-way branchin...Does Barrington's theorem about 5-way branching programs count? Bob Lipton blogged about it fairly recently.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59379595883017394972009-06-09T04:27:17.475-05:002009-06-09T04:27:17.475-05:00The existence of continuous functions that are not...The existence of continuous functions that are not differentable in any point. Probably, at the time most people believed that any continuous function is differentable almost everywhere, if we throw away some small set of points. This point of view prevailed for a long period of time until "frustrating" example due to Weierstrass. But, of course, this was not an explicitly stated conjecture...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10500162841043547472009-06-08T16:08:37.601-05:002009-06-08T16:08:37.601-05:00Another one, even if the conjecture was disproven ...Another one, even if the conjecture was disproven a short time after being stated, is the Wang's conjecture (which states that any set of Wang tiles which can tile the plane can tile it periodically). <br /><br />I think it was a kind of surprise. But OK, it was disproven just 5 years after Wang's paper.B.noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3923600159869478182009-06-08T14:21:40.482-05:002009-06-08T14:21:40.482-05:00Google turns up:
http://mathworld.wolfram.com/Mer...Google turns up:<br /><br />http://mathworld.wolfram.com/MertensConjecture.html<br /><br />A more controversial one:<br /><br />http://en.wikipedia.org/wiki/Skewes'_numberMark Wilsonhttps://www.blogger.com/profile/16382201587698895101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61591923326771407302009-06-08T14:13:38.222-05:002009-06-08T14:13:38.222-05:00I'd say conjectures in Fourier analysis go abo...I'd say conjectures in Fourier analysis go about 50-50.<br /><br />The disc multiplier conjecture turned was proved false by C. Fefferman in the early 70's.<br /><br />Most analysts thought L^2 pointwise convergence was false, until proved by Carleson in 1966.<br /><br />The Maximal Bochner-Reisz Conjecture was proved false by Tao in the mid 90's.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53144050936840137382009-06-08T13:12:34.310-05:002009-06-08T13:12:34.310-05:00NL=coNL surprised alot of people
NL=coNL was a ...<i>NL=coNL surprised alot of people</i><br /> <br />NL=coNL was a surprise but not quite the surprise it would have been a year earlier. The first surprise was the earlier paper by Lange, Jenner, and Kirsig that the logspace hierarchy collapsed at the second level. That paper certainly heavily influenced Immerman's proof. Lange, Jenner, and Kirsig do not always get their due credit in the story.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35758735168192910872009-06-08T12:38:43.168-05:002009-06-08T12:38:43.168-05:00To contribute another example, Hardy and Littlewoo...To contribute another example, Hardy and Littlewood made two conjectures about the distribution of primes: (1) the number of primes in an interval of length n is maximized by [0,n] and (2) any prime pattern that isn't impossible for modular reasons actually occurs and with a specific asymptotic density. Turns out they are contradictory.<br /><br />Regarding the Clay problems: Selberg was said to have doubted the Riemann hypothesis. I know high-profile number theorists that doubt the generalized Riemann hypothesis.Unknownhttps://www.blogger.com/profile/06229416831400925212noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2185756674441249302009-06-08T12:05:51.617-05:002009-06-08T12:05:51.617-05:00Kahn and Kalai disproving the Borsuk's Conject...Kahn and Kalai disproving the <a href="http://en.wikipedia.org/wiki/Borsuk%27s_conjecture" rel="nofollow">Borsuk's Conjecture</a> seems to fit the bill.<br /><br />Perhaps the Khot-Vishnoi(-Devanur-Saket) disproof of the Goemans-Linial conjecture, though I don't know how strongly that was believed.<br /><br />Euler's disproof of Fermat's Conjecture that 2^2^n+1 is always prime?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16761828516881652322009-06-08T11:40:50.513-05:002009-06-08T11:40:50.513-05:00Euclid conjectured that the parallel postulate cou...Euclid conjectured that the parallel postulate could be proven from the other axioms of geometry. People tried to prove it for literally thousands of years until it was shown to be independent.<br /><br />Although the result here is the same as for the Continuum Hypothesis, this is definitely a "clean" story, since the original question was about independence.Andy Parrishnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24440588414096114662009-06-08T11:25:56.598-05:002009-06-08T11:25:56.598-05:00Well, at least many famous conjectures had to be a...Well, at least many famous conjectures had to be amended for them to stand a chance of being true. For instance, there is Grothendieck's famous (short) paper on why "Hodge's general conjecture is false for trivial reasons".<br /><br />For conjectures closer to TCS,<br />I know of at least one well-known and very believable conjecture in discrete geometry (the isotopy conjecture for order types (Arnold ?)) which turned out to be wildly false. It said that for every n, given two labelled configurations of n points in the plane, such that the orientations of every triplet is the same for both, it is possible to move continuously the first configuration to the second maintaining the orientation of every triplet on the way.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8722696633225421212009-06-08T11:18:29.196-05:002009-06-08T11:18:29.196-05:00Keller's Cube-Tiling Conjecture Is False In Hi...Keller's Cube-Tiling Conjecture Is False In High Dimensions (1992)<br /> <br />by Jeffrey C. Lagarias, Peter W. Shor<br />Bull. Amer. Math. Soc<br /><br />http://www.research.att.com/~shor/papers/Keller.ps<br /><br />Not many complexity theorists now believe the Berman-Hartmanis isomorphism conjecture, thanks to developments in cryptography.<br /><br />The other one, of course, is the conjecture that the polynomial-time hierarchy is infinite... just waiting to be disproved :-)Sigma_4^p cap Pi_4^pnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82296307507959731812009-06-08T11:04:55.299-05:002009-06-08T11:04:55.299-05:00There are some examples, although not nearly as dr...There are some examples, although not nearly as dramatic as the Clay problems would be. The longest-standing one is probably Euler's generalization of Fermat's last theorem (that a_1^n+a_2^n+...+a_(n-1)^n = b^n has no positive integer solutions.) Another one is the Mertens conjecture that implies the Riemann hypothesis. A metamathematical example: the elementary proof of the prime number theorem.Anonymousnoreply@blogger.com