tag:blogger.com,1999:blog-3722233.post6936460121917102079..comments2017-06-24T09:52:46.896-04:00Comments on Computational Complexity: Other fields of math don't prove barrier results- why do we?Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-3722233.post-25441664325447636312017-05-07T21:42:06.745-04:002017-05-07T21:42:06.745-04:00First, it is not TCS in general, it is complexity ...First, it is not TCS in general, it is complexity theory. And complexity theory is about proving impossibility results, whether computation is impossible or proof is impossible are not that different from each other.<br /><br />Why BGS prove their result? I don't know. Was it considered a barrier? I am not sure.<br /><br />Why RR proved theirs? Because people spent 10 years and got no where despite initial optimism and it was natural for them to ask why. Also Razborov was working on proof complexity and formalization of circuit lower bounds if you look at his publications from that area. And that is when we started calling them barriers, right?<br /><br />Algorithms is about showing what we can, complexity theory is about showing what we cannot, and crypto is the field of making impossibility results useful.<br /><br />Why other fields don't do it? Some do like logic, algebra, combinatorics, ... Those who can prove limitations of techniques do prove them. They don't refer to them as impossibility results maybe because well it is not part of their culture. Whereas is past of the culture of complexity theory which has its roots in mathematical logic. In logic there are so many result that you can prove this and that by such and such, you cannot express this and that in such and such languages, ... Let's go back to Tarski's undefinability of truth theorem, Godel's unprovability of soundness theorem, etc.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59600236689214291352017-03-20T08:23:01.356-04:002017-03-20T08:23:01.356-04:00"other fields DO do this" - some example..."other fields DO do this" - some examples above. I would like to mention polymath project about bounded gaps between primes. The results are (a) 246 unconditionally, (b) 6 using generalized Elliott-Halberstam conjecture, and (c) the proof that with the latter bound is the limit of the sieve-theoretic method.<br /><br />However, I agree - there are MORE barrier results about P=NP questions than in number theory, for no obvious reasons: there is no reason to expect that this problem is harder than, for example, the twin prime conjecture, which waited centuries for the first substantial progress. Bogdanhttp://www.blogger.com/profile/17336734862701615202noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17402161237962028672017-03-16T04:41:36.315-04:002017-03-16T04:41:36.315-04:00I think there might be a barrier mentality in TCS ...I think there might be a barrier mentality in TCS because<br />of the different type of laws of nature. The success of engineering in many sciences is based on laws of nature which allow for in-silico experiments: with more time and hardware you get mor reliability (i.e. exactness and probability) of simulations. The laws of nature of CS (Goedel, Turing, Rice,...) imply that there are no in-silico experiments for CS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75106883797205993942017-03-15T13:33:13.718-04:002017-03-15T13:33:13.718-04:00Terry Tao's weblog discusses barrier results i...Terry Tao's weblog discusses barrier results in essays tagged 'Navier-Stokes equations', 'Euler equations', and 'finite time blowup'. These essays inspire consideration of:<br /><br />(1) What are the barriers to solving the Millennium Problem "Navier-Stokes Equation"?<br /><br />(2) What are the barriers to demonstrating (what John Preskill calls) "Quantum Supremacy"?<br /><br />(3) What are the barriers to solving the (Millennium Problem) "PvsNP"?<br /><br />Considering first the problem of Naver-Stokes blowup, Tao opines (in a comment to "Finite time blowup for Lagrangian modifications of the three-dimensional Euler equation", 29 June 2016):<br /><br />---<br />"It is widely believed that for the Euler equations (in which the viscosity is zero), finite time blowup should be possible, and perhaps even quite generic. For positive viscosity (Navier-Stokes), there is less consensus, but personally I believe it should be possible to construct some very special solutions which blow up in finite time, even if 'generic' solutions will continue to exhibit global regularity (for some vaguely defined notion of 'generic')."<br />---<br /><br />Considering second, the exhibition of Quantum Supremacy, Tao's language adapts as follows:<br /><br />---<br />"It is widely believed that for closed quantum systems (in which the evolution is unitary), Quantum Supremacy should be possible, and perhaps even quite generic. For open quantum systems (e.g. quantum electrodynamical systems), there is less consensus, but many researchers believe it should be possible to construct some very special experiments which exhibit Quantum Supremacy, even if 'generic' electrodynamical systems can be simulated with resources in P (for some vaguely defined notion of 'generic')."<br />---<br /><br />Here QED decoherence plays a role in respect to demonstrating Quantum Supremacy, that viscosity plays in respect to demonstrating Navier-Stokes blowup.<br /><br />Professor Tao is (of course) open to the possibility that Navier Stokes equations do not blowup. E.g., Tao's "Why global regularity for Navier-Stokes is hard" (18 March, 2007) considers "Strategy 3: Discover a new method which yields global smooth solutions."<br /><br />Transposing to Quantum Supremacy, "Strategy 3" becomes "Discover general quantum simulation methods that for evolution promised to be QED, require only polynomially many state-space dimensions." Garnet Chan's well-attended plenary lecture at last month's QIP 2017 "Simulating quantum chemistry on a classical computer" (YouTube yYwUQe2Aorw) made such a strong (albeit empirical) case for "Strategy Three", that even the most ardent Quantum Supremacists were observed to play hooky from subsequent QIP lectures, instead engaging in animated conversations with Professor Chan. QIP 2017 was fun! :)<br /><br />Considering third, tseparating P from NP, Tao's language adapts as follows:<br /><br />---<br />"It is widely believed that the class of languages in P is a proper subset of the class of languages in NP, promised that formal proofs of complexity class-membership are provided. For the broader problem in which class-membership is decided oracularly, there is less consensus, but many complexity theorists believe it should be possible to construct some very special proof techniques that separate P from NP, even if complexity class-membership is undecidable for 'generic' languages (for some vaguely defined notion of 'generic')."<br />---<br /><br />In a nutshell, Navier-Stokes blowup is incompatible with viscosity, Quantum Supremacy is incompatible with QED, and separating P from NP is incompatible with class-oracles. We thus conceive a 21st century in which:<br /><br />• Navier-Stokes flows cannot blow up, and <br />• Quantum Supremacy cannot be demonstrated, and <br />• PvsNP (with oracular promises) cannot be proved <br /><br />Effectively we already live in this world, and (as was seen at QIP 2017) it's not so bad! :)John Sidleshttp://tinyurl.com/ISH-QIP-2017-rump-slidesnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64574102100573136322017-03-15T13:28:50.727-04:002017-03-15T13:28:50.727-04:00I think there is a difference between TCS and othe...I think there is a difference between TCS and other fields. Maybe it's because complexity theorists are already used to proving that things are hard, so it's natural to also try to prove that certain proofs are hard. Computer scientists also seem to like to explore specific models of computation, and a proof technique can be considered a very specific model of computation. So proving the limitations of a proof technique is already very close to what many complexity theorists are already doing.<br /><br />TL;DR: TCS likes lower bounds so it's natural that they dwell on "lower bounds" for proof techniques.Patrickhttp://www.blogger.com/profile/09956803907225354566noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62203295837601674082017-03-15T10:59:09.979-04:002017-03-15T10:59:09.979-04:00Great comments!
I rephrase my question in light of...Great comments!<br />I rephrase my question in light of them:<br /><br />While other fields have some barrier results, they don't seem to dwell on them. They don't have workshops on barrier methods. When a barrier to a technique is proven they don't try to apply it to all other open problems.<br /><br />In TCS we seem to do this (This is not a criticism). <br /><br />1) Is Bill right- is there a DIFFERENCE in mentalities about<br />barrier method in TCS vs other parts of math?<br /><br />2) if so then why is this true?GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5332474421606268672017-03-14T05:18:19.512-04:002017-03-14T05:18:19.512-04:00Before FLT was proved, I think it was understood w...Before FLT was proved, I think it was understood why an infinite descent approach wouldn't work. Something connected with the structure of the Tate-Shafarevich group.<br /><br />There are also comments on Tao's blog and polymath project indicating that the Zhang/Maynard methods probably can't reach the full twin prime conjecture.Lievenhttp://www.blogger.com/profile/01537820436390730307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25196372620754636812017-03-14T02:25:53.199-04:002017-03-14T02:25:53.199-04:00I don't know if this is exactly what you are l...I don't know if this is exactly what you are looking for, but before Borel determinacy was proved, Harvey Friedman showed that any proof of it would require the axiom of replacement. I'm not sure how surprising people found that at the time though.Patrickhttp://www.blogger.com/profile/09956803907225354566noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85624212495890407382017-03-13T16:57:34.265-04:002017-03-13T16:57:34.265-04:00"Entropy cannot decrease under symplectomorph..."Entropy cannot decrease under symplectomorphic dynamical flows. This is important because all successful physical theories (both classical and quantum) are dynamically symplectomorphic."<br /><br />It's interesting that physicists and complexity theorists alike profess articles of faith in respect to oracles.<br /><br /><b>Physicist</b> No measurement device can "oracularly" determine the position and momentum of a Newtonian particle.<br /><br /><b>Complexity theorist</b> P can be separated from NP even when class membership is "oracularly" determined.<br /><br /><b><i>Vive la différence?</i></b> Physicists assume that (unphysical) oracles <i>don't</i> exist, whereas complexity theorists assume (undecidable) algorithmic oracles <i>do</i> exist. <br /><br />Hmmmmmm …<br /><br /><b>Open question</b> Might a refrigerator whose working fluid comprised Chaplygin Sleigh molecules violate the Second Law? To my surprise — and delight — an arXiv search shows that work in this area is getting underway (arXiv:1603.00369)! :)John Sidleshttp://tinyurl.com/ISH-QIP-2017-rump-slidesnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83360005245887067102017-03-13T14:34:42.262-04:002017-03-13T14:34:42.262-04:00Parity barrier in sieve theory?Parity barrier in sieve theory?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8175934918408598982017-03-13T13:14:37.127-04:002017-03-13T13:14:37.127-04:00All great examples- lets see why they are not QUIT...All great examples- lets see why they are not QUITE what I had in mind<br /><br />1) FM Theorem- did they show you could not have computable witnesses BEFORE proving it and hence this was considered a barrier to a proof OR was this theorem about comp wit done after it was proven? I suspect after-the-fact. but if not then YES would qualify<br /><br />2) CH and countrexamples and 5th degree can't be solved-- these tend to show that what you want to prove is FALSE (though in CH that might not be quite right-- at least showing ZFC--> CH can;t be done) and indeed being FALSE is<br />a barrier to showing something is true.<br /><br />I am looking for a theorem T which is open and people think IS true and they prove certain techniques won't work to prove T, but not proves that T is false.<br /><br />THanks for clarifying my question!GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21934523006616676572017-03-13T13:00:07.602-04:002017-03-13T13:00:07.602-04:00Positive results are hard, yet papers need to be w...Positive results are hard, yet papers need to be written (for graduation, jobs, promotions, etc)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86350160276592200392017-03-13T12:54:54.897-04:002017-03-13T12:54:54.897-04:00Arguably, the genesis of modern mathematics is the...Arguably, the genesis of modern mathematics is the Abel-Ruffini theorem, which states the impossibility of a general method for solution of quintic equations by radicals.<br /><br />Is this different from what you had in mind?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63640360425767465922017-03-13T12:37:59.998-04:002017-03-13T12:37:59.998-04:00I believe that Mathematical Logic has such example...I believe that Mathematical Logic has such examples.<br /><br />1. Friedberg-Muchnik Theorem. There is the observation that diagonalization techniques using computable witnesses will not work. I believe this was explicitly known.<br /><br />2. Continuum hypothesis. Both forcing and Boolean valued models were radically new techniques. Not sure whether the *need* for new techniques was explicitly mentioned in previous papers.<br /><br />Finally, one could argue that many of the *counterexamples* in Mathematics are a kind of statement about the insufficiency of certain techniques. (Carmichael numbers show that Fermat's Little Theorem is not sufficient to exclude ALL nonprimes, continuity arguments do not suffice to prove differentiabilty, etc.)CSProfhttp://www.blogger.com/profile/07212822875614144307noreply@blogger.com