tag:blogger.com,1999:blog-3722233.post5910064276342137112..comments2021-09-14T11:25:32.611-05:00Comments on Computational Complexity: But seriously now folks- what do you make of barrier results?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-3722233.post-28628091827045044162010-04-13T03:25:56.335-05:002010-04-13T03:25:56.335-05:00Look at Jeff Lagarias's paper about the 3n+1 c...Look at Jeff Lagarias's paper about the 3n+1 conjecture and all the approaches to it that can't work.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88790414313855953702010-04-08T09:19:03.855-05:002010-04-08T09:19:03.855-05:00Hmmmm ... to state the previous result more provoc...Hmmmm ... to state the previous result more provocatively: arguably it would be a <i>disaster</i> for complexity theory, if P≠NP were proved by some ingenious technical trick ... because we would have the proof without fully understanding the obstructions ... the latter task being (arguably) more important than the former.<br /><br />There is plenty of mathematical precedent for this point of view: Grothendieck was vastly dissatisfied with Deligne's proof of the Weil conjectures, for precisely this reason.<br /><br />These considerations amount to saying that mathematics is largely about the understanding of barriers, and therefore, we need all the barrier results we can get.<br /><br />This point-of-view seems very reasonable to me ... even though (obviously) it is not the <i>whole</i> story.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10749558131985472992010-04-08T09:02:45.945-05:002010-04-08T09:02:45.945-05:00Hmmm ... yet another class of answers to GASARCH&#...Hmmm ... yet another class of answers to GASARCH's question <i>"What do you make of barrier results?"</i> can be given using one of Dick Lipton's most useful phrases: "Barrier results are theorems about <i>proof technology</i>." In detail: "Barrier theorems assert that such-and-such a class of proof technology does not exist."<br /><br />This point-of-view enlarges the class of well-known barrier results to include examples like: "The only associative normed division algebra over the complex numbers are the complex numbers themselves" and "The only normed division algebras over the reals are the real numbers, the complex numbers, the quaternions, and the octonions."<br /><br />These barrier theorems appear trivial to modern eyes ... yet they definitely were not trivial to (for example) William Hamilton's generation.<br /><br />From this point of view, the text <i>A=B</i> contains innumerable examples of barrier result, relating specifically to the existence versus non-existence of broad classes of combinatoric identities.<br /><br />Obviously, we are very far from understanding P=?=NP at this level ... we are only beginning to perceive even the obstructions to a straightforward proof ... and therefore you can count me as an enthusiast for every kind of barrier result. More please!John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57095547643776834622010-04-08T00:01:24.219-05:002010-04-08T00:01:24.219-05:00If I recall the proof is that there is no general ...If I recall the proof is that there is no general equation to give you the roots of a degree 5 polynomial.Jacob Schlatherhttps://www.blogger.com/profile/03164381598728074438noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82850729403837355492010-04-07T17:16:44.929-05:002010-04-07T17:16:44.929-05:00I am not sure about degree 5<= polynomials, but...I am not sure about degree 5<= polynomials, but my guess is that people were trying to find formulas for solving them. The reason for this is that as far as I remember Galois's work is considered revolutionary. The right place to ask this question is FOM mailing list:<br />http://www.cs.nyu.edu/mailman/listinfo/fom/<br /><br />Also it is a natural place to ask for more negative results.<br /><br />ps: I searched their archive for Galois, did not find an answer.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29639516570378200352010-04-07T14:49:05.186-05:002010-04-07T14:49:05.186-05:00In physics, Richard Feynman set forth a barrier hy...In physics, Richard Feynman set forth a barrier hypothesis in a 1982 article <i>Simulating physics with computers</i>, to the effect that "The full description of quantum mechanics, ... because it has too many variables, <i>cannot be simulated</i> with a normal computer" (emphasis Feynman's).<br /><br />Ever since 1982, Feynman's barrier has been dissolving; first slowly, but nowadays more quickly. For quantum chemists it is pretty much totally dissolved; for condensed matter physicists it is largely dissolved, and for quantum information theory physicists the dissolution of the barrier is just now getting underway.<br /><br />The key has been to recognize that if we look at dynamics with the geometric and category-theoretic toolset of Mac Lane and Arnol'd, then quantum and classical dynamics don't look all that different. As for the large-dimension barrier that Feyman pointed-out, we can dissolve it for quantum systems via the same mechanism that molecular simulationists exploit in classical systems: the dynamical compression of trajectories. <br /><br />Classical mechanics calls these compressive dynamical mechanisms "thermostats"; quantum dynamics calls them "Lindblad processes"; but this distinction is mathematically arbitrary, because when regarded from the Mac Lane/Arnol'd <a href="http://faculty.washington.edu/sidles/Litotica/QSE_JCP_commutative_color.pdf" rel="nofollow">geometric/category-theoretic point-of-view</a> they are seen to be mathematically the same mechanism.<br /><br />In the practical world, we see that thermostats and Lindblad processes are ubiqutious ... in fact, we don't presently have <i>any</i> technology and/or experiments that provably probe the large-dimension barriers that Feynman discussed.<br /><br />Similarly, with respect to P versus NP ... how often in the real world do we deal with problems that are NP-complete? Isn't there---in practice---always extra informatic structure available to solve real-world problems ... in the same way that thermostats and Lindblad processes are ubiquitously available to help us simulate dynamical systems?<br /><br />Now, in complexity theory there *IS* one big exception: cryptography. And in quantum physics too there is one big exception: quantum computing. That is why the deepest mysteries of complexity theory and quantum mechanics are so often encountered in cryptographic and quantum computing settings.<br /><br />----------<br /><br />@article{Feynman:82, Author = {R. P. Feynman}, Journal = {International Journal of Theoretical Physics}, Number = {6--7}, Pages = {467--488}, Title = {Simulating physics with computers}, Volume = 21, Year = 1982}John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41933190984055067802010-04-07T14:47:04.510-05:002010-04-07T14:47:04.510-05:00Anon 5: Thanks for all of those examples.
For 5th ...Anon 5: Thanks for all of those examples.<br />For 5th degree equation--- were they trying to show that there WAS such an equation and were trying to rule out approaches to it? I do not know.<br /><br />In all of the examples the naysayers had it right. If P vs NP follows that pattern then we may have P = NP (which would shock<br />Lance Fortnow, but Richard Lipton wouldn't be too surprised.)GASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84184540391600908902010-04-07T14:42:57.709-05:002010-04-07T14:42:57.709-05:00Also these kind of result have been usually first ...Also these kind of result have been usually first state as some object does not exists, but later because of nonexistence of these objects we were able to prove/construct/discover other theorems/objects/algorithms.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55216020789433268152010-04-07T14:37:57.156-05:002010-04-07T14:37:57.156-05:00Galois's work and degree 5<= polynomials, i...Galois's work and degree 5<= polynomials, impossibility of trisecting, impossibility of constructing third root of 2, unprovability of fifth axiom of Euclid from the rest of his axioms, undecidability of Diophantine equations, ... and of course Godel and Cohen's work, and also many infinite set theoretical statements.<br /><br />I guess there are more. It seems that it has always been that there was a problem that people were interested in for some time and many tried to solve them, but at some point someone notices that there is the possibility that they are impossible to solve. Also the possibility of formalizing things is important, without formalization of what are the methods, we can not even express that these methods can not solve those problems preciously, let alone proving that the methods do not work.<br /><br />If I was pessimistic, I would say that there is the possibility that ZFC+strong cardinal axioms can not decide P vs NP, and that even this is not provable in it, and so on forever ... but I am not. :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62434045984206800232010-04-07T13:04:48.616-05:002010-04-07T13:04:48.616-05:00If we prove P neq NP then everyone can stop lookin...<i>If we prove P neq NP then everyone can stop looking for worst case NP algorithms.</i><br /><br />Will we then also know that the multiplication of two n-bit integers requires super-linear size circuits?Stasysnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18563159656647015582010-04-07T12:44:02.925-05:002010-04-07T12:44:02.925-05:00P vs NP itself is a barriers result. If we prove ...P vs NP itself is a barriers result. If we prove P neq NP then everyone can stop looking for worst case NP algorithms.Granthttps://www.blogger.com/profile/02407492494639217331noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23951751428700963962010-04-07T12:03:17.769-05:002010-04-07T12:03:17.769-05:00We need "barrier problems", no question....We need "barrier problems", no question. But when concentrating on P vs. NP and the like, we often forget that the real barriers of our understanding in complexity consist of much "simpler" problems. Like the following one:<br /><br />For a (0,1) matrix A, let t(A) be the smallest number t such that one can write A as a sum (over the reals) of t 0-1 matrices such that the 0-entries in each of these matrices can be covered by at most t all-0 their submatrices. <br /><br />Easy counting shows that n-by-n 0-1 matrices A with t(A)>n^{1/2} exist.<br /><br />Problem: Exhibit an EXPLICIT 0-1 matrix A with t(A)>n^c for an arbitrary small constant c>0.<br /><br />Be it so “simply,” this is a more than 30 years old problem in computational complexity! Such a matrix would give us the first super-linear lower bound on the size of log-depth circuits. The first real progress in this field. This problem (and many similar combinatorial ones) sound much simpler. If we cannot solve such "simple" problems, what a solution of P vs. NP problem will give us? Especially, when we all "know" that P\neq NP. We will still be unable to solve these "simpler" problems.Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39976905886053667632010-04-07T10:29:16.981-05:002010-04-07T10:29:16.981-05:00Fermat's Last Theorem comes to mind, but often...Fermat's Last Theorem comes to mind, but often these results came in the form of someone saying "I HAVE A PROOF OF FLT!" when they didn't.<br /><br />Infinite descent is not sufficient, nor is the method employed by Gabriel Lame (due to the fact that not all rings have unique factorization).Regular Everyday Normal Adjunctnoreply@blogger.com