tag:blogger.com,1999:blog-3722233.post3100230548292801563..comments2020-02-19T03:43:18.369-05:00Comments on Computational Complexity: P = NP and the WeatherLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-46391408964939575042013-08-28T02:29:41.889-04:002013-08-28T02:29:41.889-04:00I think the fundamental problem with using the exa...I think the fundamental problem with using the example of weather prediction is that finding the right model in practice is not a problem in which complexity theory is very useful. In practice finding the right model, and mathematical modeling, in general, are not decision problems as we think of them in terms of complexity. (Also how would you verify if you had the "right model" a priori any way?) Mathematical modeling often requires very specific domain knowledge (eg weather, biology) as well as wise choice of the variables that capture that knowledge and their nature (eg discrete, stochastic, etc.) Where complexity theory is really useful in modeling is helping determine how quickly and efficiently as solution can be found if at all with known algorithms, or if new algorithmic work is necessary, and how many resources such as memory, CPUs, and time would be necessary to find a suitable solution for the model. This latter point on resources is extremely nontrivial because this could be the difference between having a model you can use meaningfully and not having one at all (i.e., it's a beautiful model, but you'll need to wait a few years to get any results.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47839543612468350002013-08-25T20:56:54.548-04:002013-08-25T20:56:54.548-04:00An NWP model solve a set of partial differential e...An NWP model solve a set of partial differential equations for which nobody knows how to compute an analytical solution. Almost all approximation algorithms (explicit and implicit time integrators) are polynomial in nature, but the time require to run them is large because<br /><br />- the timestep is limited by the CFL criterion for explicit method. Considering that the equations of the fluids can support acoustic and gravity wave (fast moving wave), the constrain can be very important. Even if an implicit method is used, accuracy (precipitation and turbulence duration can be short) impose a limit on the time step.<br /><br />- the grid required to run a simulation over the whole planet at high resolution (say less than 1 km in the horizontal and a few meters in the vertical) is very large. Problem get worse when a latlon grid is used because there is a singularity at the pole.<br /><br />- if you google about data assimilation methods like extended kalman filter or 4D-VAR, you will see that producing initial conditions are probably a place where P=NP would imply improvement in the models, but P=NP would change nothing about the main problem : the full covariance matrix is quite big and problematic to fit in the memory of a real computer.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38200625130225716802013-08-23T11:31:01.421-04:002013-08-23T11:31:01.421-04:00--------------------
Leen's Great Truth "...--------------------<br /><b>Leen's Great Truth</b> "People shouldn't however take [complexity theoretic] matters too seriously and dig deep into the text [of complexity-theoretic narratives such as <i>The Golden Ticket</i>]"<br />--------------------<br /><br />Leen, you have expressed a Great Truth whose dual Great Truth is worth contemplating,<br /><br />--------------------<br /><b>Leen's Dual</b> "People should take complexity theoretic matters very seriously and should dig deep into the texts of complexity-theoretic narratives [such as <i>The Golden Ticket</i>]"<br />--------------------<br /><br />Dick Lipton and Ken Regan's recent <i>Gödel's Lost Letter</i> essay, titled <b><a href="http://rjlipton.wordpress.com/2013/08/10/move-the-cheese/" rel="nofollow">"Move the Cheese"</a></b>, addresses some of the reasons why engineers in particular should embrace Leen's dual. And an even finer Leen-dual essay (as it seems to me) is Wendell Berry's <i>Thomas Jefferson Lecture in the Humanities for 2012</i>, titled <b>"<a href="http://www.neh.gov/about/awards/jefferson-lecture/wendell-e-berry-lecture" rel="nofollow">It All Turns On Affection</a>"</b>. <br /><br />Berry's essay (as I read it) naturalizes and generalizes the foundational themes of Bell Thurston's well-beloved (and much-cited) essay "On Proof and Progress in Mathematics" (arXiv:math/9404236), and applies Thurston's themes broadly and wisely to some of the 21st century's urgent challenges.<br /><br /><b>Summary</b> The STEM community's "cheese" has moved; far too many young STEM "mice" are starving for lack of family-supporting jobs; essayists like Wendell Berry and William Thurston speak to the nourishment that all mice (of all ages and all occupations) require; in particular the traditional STEM cheeses of "quantum supremacy and the complexity zoo" are destined to be supplanted by new, more abundant cheeses; if we are diligent, imaginative, daring, and lucky, perhaps these new STEM cheeses may even prove to be more tasty and nourishing than the traditional STEM cheeses.<br /><br /><b>Conclusion</b> Seek new cheese bravely!John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23434289647780571692013-08-23T06:23:38.150-04:002013-08-23T06:23:38.150-04:00Apparently a simple example can lead to very deep ...Apparently a simple example can lead to very deep (weird?) thoughts and Lance was right that he shouldn't have used a difficult problem, like the weather, as an example but rather an easy one, like a cure for cancer. Seems to me that there is indeed a question of does there exist a model of reasonable size that can be used to predict the weather (looks a bit like an NP-problem doesn't it?). If it does, and P=NP, then we can find it. (Guess one; use it; don't toss it as long as it predicts correctly; seems a perfect poly-time guess-verify strategy, that must work provided such a model exists). <br /><br />The "Golden Ticket" is a nice, easy going, introductory, popular science book(let) about one of the most important questions of our time. As such, it is an unparallelled success. People shouldn't however take matters (and themselves) too seriously and dig deep into the text and dig up all sorts of ... let me just stop there.Leenhttps://www.blogger.com/profile/10467530858979254031noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87808438508863215392013-08-23T05:50:32.325-04:002013-08-23T05:50:32.325-04:00As a followup to Case 2B, a recent preprint "...As a followup to Case 2B, a recent preprint <b>"<a href="http://arxiv.org/abs/1306.3995v1" rel="nofollow">Boson-Sampling in the light of sample complexity</a>"</b> (arXiv:1306.3995), by Christian Gogolin, Martin Kliesch, Leandro Aolita, and Jens Eisert, discusses John Preskill's notion of "quantum supremacy" in light of the same class of questions that Lance's weather example raises.<br /><br />The overall point (perhaps) is that 20th century researchers envisioned <b><a href="http://quantumfrontiers.com/2012/07/22/supremacy-now/" rel="nofollow">an utopian future of quantum supremacy</a></b> in which quantum computers solved problems that provably were not in P. Now in the 21st century, we are coming to concretely appreciate the reasons why a future in which <i>none</i> of the envisioned elements of quantum supremacy are achievable — even in principle! — might be both more utopian and more realistic that the traditional quantum vision … and therefore more hopeful and interesting.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41233647667963082742013-08-23T05:31:30.748-04:002013-08-23T05:31:30.748-04:00In 2008, Lance Fortnow's reviewer wrote to me:...In 2008, Lance Fortnow's reviewer wrote to me:"A Turing machine cannot diagonalize against itself as the author claims he can do without proof. I urge the author to write the program for this machine to realize the impossibility of this task". The paper contained a Prolog meta-interpreter where every line of a program is a Turing machine that diagonalizes against itself (semantically), using Fuzzy Logic Programming.<br /><br />Since Fuzzy Logic Programming is a foreign area for complexity theorists. In 2009/2010, I modified my proof using the lambda-calculus Kleene-Rosser paradox which Laszlo Babai (ToC) rejected as the Kleene-Rosser paradox recognition problem is undecidable In 2011, Luca Trevisan (JACM) rejected a similar paper on the grounds that the Kleene-Rosser paradox is undefined.<br /><br />In 2013, I proved (in JACM submission) that <br /><br />1. KRP is defined iff KRP is undefined.<br />2. KRP is decidable iff KRP is undecidable, over both the lambda-calculus and Turing machine.<br /><br />==> All mathematical theories are inconsistent.<br /><br />It is (philosophically) trivial to realize in order to effectively model a set of infinite numbers, one needs a mathematical language whose alphabet MUST be infinite.<br /><br />See: http://kamouna.wordpress.com, for discussions with the FOM (Foundations of Mathematics) mailing list.<br /><br />Best,<br /><br />Rafee Kamouna.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29653325520772073922013-08-22T18:40:32.253-04:002013-08-22T18:40:32.253-04:00It may be that the optimal weather model is itself...It may be that the optimal weather model is itself computationally intractable (beyond P or NP). Quite plausibly, one would need to model an exponentially large number of elements to obtain optimal estimates. The real question is, what is the information-theoretically-optimal weather prediction?Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22699036466227910922013-08-22T13:50:03.960-04:002013-08-22T13:50:03.960-04:00The weather example exposes several more marginal ...The weather example exposes several more marginal cases:<br /><br /><b>Case 1</b> Future weather can be predicted by a machine that runs in P (as an oracle correctly assures us), but whose runtime is not <i>provably</i> in P. Is weather prediction <i>effectively</i> in P?<br /><br /><b>Case 2</b> It turns out that future weather is random, but sampling the weather <i>distribution</i> is NP-hard. Bob's start-up company has a PTIME weather-simulation algorithm, that samples from a distribution that requires exponential resources (in space and/or time) to distinguish from the "true" NP-hard weather distribution. Is weather simulation <i>effectively</i> in P?<br /><br /><b>Case 2B</b> Bob's start-up company has a PTIME quantum-simulation algorithm that (as with the weather-simulation algorithm) produces simulated measurements that are sampled from a distribution that requires exponential resources (in space and/or time) to distinguish from the "true" distribution of measurements. Is quantum simulation <i>effectively</i> in P?<br /><br /><b>Case 3</b> A proof is found that PvsNP is undecidable in homotopy type theory (HOTT), but the proof does not extend to a stronger axiom system (ZFC, for example). Should the Clay Institute rescind its PvNP Millenium prize, on grounds that the problem is uninteresting? More broadly, how strong does an axiom system have to be, for a proof of PvNP undecidability in that system to cause us to conclude that PvNP is "really" undecidable, such that we abandon the search for a "meaningful" proof?<br /><br />The point is that these marginal questions can be settled only by (1) strong proofs <i>and</i> (2) refined definitions <i>and</i> (3) (possibly) adjusted axioms.<br /><br /><b>Summary</b> PvNP is a triple-threat problem, with plenty of real-world implications.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81204370510062226342013-08-22T09:39:25.473-04:002013-08-22T09:39:25.473-04:00I'm not having trouble even if I log out of Dr...I'm not having trouble even if I log out of Dropbox but here is a <a href="https://docs.google.com/file/d/0B3Yf--R4oxczQ0lwZ3hxamlZc3c/edit?usp=sharing" rel="nofollow">link</a> to the same file on Google Drive.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32237041416968580932013-08-22T09:29:31.510-04:002013-08-22T09:29:31.510-04:00The link to Dean Foster's piece appears to be ...The link to Dean Foster's piece appears to be broken: It leads to a page that just says "Dropbox", with no other content. Permissions problem, perhaps?Varshahttps://www.blogger.com/profile/11526849015267871764noreply@blogger.com