tag:blogger.com,1999:blog-3722233.post2395371995874219935..comments2020-11-28T12:01:40.731-06:00Comments on Computational Complexity: Is Complexity Math or Science?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger37125tag:blogger.com,1999:blog-3722233.post-57272145965285373192010-05-19T13:30:36.176-05:002010-05-19T13:30:36.176-05:00"Efficient computation occurs not just in com..."Efficient computation occurs not just in computers but in biological systems, physical systems, chemical systems, economic systems and much more."<br /><br />I would propose that the capacity for abstraction is a primary driver of increasing complexity. Efficiency simply encapsulates a contiguous or direct trajectory. <br /><br />Another primary diver of complexity is concurrence. <br />While science and math do have the capacity for abstraction, neither science nor math have the capacity for concurrence.<br /><br />Concurrence means clocks for every granule and every granule a clock.<br /><br />Modern microprocessors while marvelous feats of engineering, are still the only granule. <br /><br />Even threading isn't real concurrence nor is cloud computing or clusters.<br /><br />They all require software compilers which is a form of predetermination. <br /><br />If software were a key to handling genuine complexity, then as OOP and OOD moved us away from the machine there should have been a new machine to take their place.<br /><br />We really need start thinking in terms of metabolisms not systems.<br /><br />Respectfully<br />dwc<br /><a title="The Rational Model of Complex Mechanisms" href="http://www.rationalmechanisms.com/default" rel="nofollow">RMCM©</a>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65537157848333434672010-05-14T07:20:24.835-05:002010-05-14T07:20:24.835-05:00If I had a wish for computational complexity, it w...If I had a <i>wish</i> for computational complexity, it would be that the "result" (or at least a result) would be something as useful and understandable and influential as the <a href="http://en.wikipedia.org/wiki/Design_Patterns" rel="nofollow">Gang of Four's <i>Design Patterns</i></a>. But not for general object-oriented programming, but rather for search and optimization problem-solving.<br /><br />I'm hopeful that a lot of the trouble you-all are feeling and expressing might dissipate if we question these sorts of dichotomies. Philosophically, whether somebody claims they're doing "theory" or "practice", or "engineering" vs "science", or "applied" or "pure" mathematics… they all are <i>for</i> something, and it might be more helpful to think about the kinds of problems they solve.<br /><br />So: if there were a real, useful design patterns effort arising from the broader work in Computational Complexity, that might help address these confusing issues, is all I'm saying.Vagueryhttps://www.blogger.com/profile/13410026802332846187noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73228909544536804702010-05-12T18:04:31.922-05:002010-05-12T18:04:31.922-05:00This is pretty darn impressive for 1948!
No, it i...<i>This is pretty darn impressive for 1948!</i><br /><br />No, it is not. It is completely normal from von Neumann.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33138982197388203532010-05-12T17:34:29.757-05:002010-05-12T17:34:29.757-05:00Computation doesn't happen in biological syste...<i>Computation doesn't happen in biological systems ...</i><br /><br />Hmmm ... the boundaries between logic, combinatorics, and dynamics can be *very* hard to pin down in *any* field ... especially in biology! <br /><br />For example, there's a 1948 letter from von Neumann to Wiener, in which von Neumann guesses,on purely informatic gounds—and years in advance of Watson and Crick—as follows: <br /><br /><i>"Certain traits of the gene-enzyme relationship, of the behavior of some mutants, as well as some other phenomena, seem to emphasize some variants of self-reproductivity, which one would be led to investigate on purely combinatorial grounds as well. E.g.: Self-reproductivity may be symbolized by the schema A→A. What about schemata like A→B→C→A, or A→B→C→D?"</i><br /><br />This is pretty darn impressive for 1948!John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18205522969683680402010-05-12T15:56:12.541-05:002010-05-12T15:56:12.541-05:00Multiplication, and all computation, is a mathemat...<i>Multiplication, and all computation, is a mathematical abstraction.</i><br /><br />Addition happens in nature. You take four things join them with three things and now you have seven things. Addition then is a mathematical abstraction as much as Newton's law are a mathematical abstraction.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37290967538495095732010-05-12T14:52:12.282-05:002010-05-12T14:52:12.282-05:00Computation doesn't happen in biological syste...Computation doesn't happen in biological systems unless you believe that cell division performs multiplication by two. Multiplication, and all computation, is a mathematical abstraction.Patrickhttps://www.blogger.com/profile/16816252455472704262noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83876542721175097112010-05-11T17:32:10.064-05:002010-05-11T17:32:10.064-05:00The latin root *scientia* generally means knowledg...The latin root *scientia* generally means knowledge, which I understand is not the common use because people usually mean physics, chemistry, biology, maybe math, and engineers are suspect. In any case, the more general knowledge is useful because it isn't restricted by discipline or the objects of study. Aristotle, for example, thought there were two types of knowledge; one involving those objects whose quantification he felt was not in question, and the other includes relations between objects which, in society, would mean that we can develop knowledge or science (of course, he didn't know latin, so maybe he couldn't be a scientist, ha ha).Doug Mouncehttps://www.blogger.com/profile/10917054134517643425noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55326790603368613152010-05-10T20:30:00.446-05:002010-05-10T20:30:00.446-05:00"How applied mathematics became pure" by..."How applied mathematics became pure" by Penelope Maddy<br /><br />http://www.pgrim.org/philosophersannual/pa28articles/maddyhowapplied.pdfAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55615397728579021602010-05-10T14:22:41.971-05:002010-05-10T14:22:41.971-05:00Something is a science if, at the end of all our t...Something is a science if, at the end of all our theorizing and hypothesizing, you can test out the idea and see if it matches up with experience. If they don't agree, we toss the idea out or revise and retest. When that all-important step is left out, we can't call what we're doing science. The observable world is the final arbiter.Kennethhttps://www.blogger.com/profile/01449820074704102130noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12745141338487273622010-05-10T14:03:13.743-05:002010-05-10T14:03:13.743-05:00Geometers should care about the real world's g...Geometers should care about the real world's geometry. Fortunately, CS folk are more in touch with reality.<br /><br />Experiments on "protein structure" prediction? I forgot that proteins were taught in CS101.<br /><br />Astronomy is science because they too are working with a model that they may confirm or invalidate. Their "observations" are experiments.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37757082221136715372010-05-09T20:03:05.023-05:002010-05-09T20:03:05.023-05:00Yet another distinguished essay that bears on Lanc...Yet another distinguished essay that bears on Lance's question is William Thurston's <a href="http://arxiv.org/abs/math/9404236v1" rel="nofollow"><i>On Proof and Progress in Mathematics</i></a> ... <br /><br />Thurston reviews (numerous) respects in which mathematics itself is not solely about proofs—his case history of the development of fibration theory is uniquely insightful—and he suggests that a good question to ask is "What is it that mathematicians accomplish?", and more specifically, "How do mathematicians advance human understanding of mathematics?" <br /><br />IMHO Thurston's questions are good ones to ask about complexity theory too. Even after we narrow our attention to dynamical simulation theory, they *still* are very good, very deep questions.<br /><br />Thurston's preface to Daina Taimina's <i>Crocheting Adventures with Hyperbolic Planes</i> covers the same ideas in a less technical way, that perhaps for some people will be even more enjoyable.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44716118762936516732010-05-09T07:33:14.960-05:002010-05-09T07:33:14.960-05:00isn't that a very blurry distinction?
It is ...<i>isn't that a very blurry distinction? </i><br /><br />It is a <i>somewhat</i> blurry distinction. Furthermore I can think of several instances where what people do and what the field is can be very far apart. <br /><br />Think back to the days of strong AI in the 70s, when AIers were in the business of making grand empty promises about future advances. This doesn't mean that AI is the field dedicated to grand empty promises. AI is the study of grand and very difficult <i>problems</i>---not promises. AIers just lost track of their true goal for a while.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28800240895317754812010-05-09T05:23:38.671-05:002010-05-09T05:23:38.671-05:00Lance was not asking about what "complexitist...<i>Lance was not asking about what "complexitists" do, but what complexity theory is.</i><br /><br />But just like Michael Mitzenmacher said ... isn't that a very blurry distinction? Didn't Wittgenstein (for example) make great progress by asking, not what philosophy is, but what do philosophers <i>do</i>? And similarly Turing, by asking not what computing is, but what computers <i>do</i>? And Gauss by asking, not what space is, but what surveyors <i>do</i>? And Mac Lane, by asking not what mathematics is, but what it is that fundamental mathematics <i>does</i>? <br /><br />This principle perhaps is the point behind Mac Lane's observation, that "Mechanics developed by the treatment of many specific problems" ... and not by discerning the symplectic roots of mechanics <i>ab initio</i>.<br /><br />If we ask "What do complexity theorists do?"—as a matter of daily professional practice—they analyze complex dynamical systems. And these dynamical systems include both the "tightly-targeted proof machines" that PWZ focus upon, and the ever-expanding class of broad-spectrum simulation machines, such as are fundamental to modern synthetic/systems biology and condensed matter physics.<br /><br />The progress in recent decades of every kind of dynamical engine has been astounding ... from proof engines on Boolean state-spaces to large-scale quantum simulations on tensor network state-spaces ... the pace of progress makes Moore's Law look stately.<br /><br />Thus, there's no need to wait for new synthetic sweeps to originate in complexity theory ... because all of STEAM is being transformed <i>right now</i>, by synthetic sweeps that originated in complexity theory.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47863537621688037452010-05-08T21:24:52.618-05:002010-05-08T21:24:52.618-05:00It does, if Lances' question was on computatio...<i>It does, if Lances' question was on computational complexity as practiced by complexitists. </i><br /><br />As Michael Mitzenmacher said, careful with overgeneralizations. Moreover, Lance was not asking about what "complexitists" do, but what complexity theory is.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19744339612601057622010-05-08T13:21:29.043-05:002010-05-08T13:21:29.043-05:00Similarly, once we have settled on a specific ques...<i>Similarly, once we have settled on a specific question like P versus NP it becomes a mathematical question but that does not make computational complexity mathematics.</i><br /><br />It does, if Lances' question was on computational complexity as practiced by complexitists. <br />You are arguing on what computational complexity <b>should</b> be, not on what it is in practice.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69685561083087992152010-05-08T10:54:55.212-05:002010-05-08T10:54:55.212-05:00In the mathematical sciences the act of working on...In the mathematical sciences the <i>act</i> of working on a given problem may be may be purely mathematical but that does not make the <i>field</i> mathematics. Once you have some population genetics model understanding its behavior is a mathematical process (as well as part of the field of population genetics) but that does not make population genetics mathematics. Similarly, once we have settled on a specific question like P versus NP it becomes a mathematical question but that does not make computational complexity mathematics.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30422477134360598322010-05-08T10:38:43.259-05:002010-05-08T10:38:43.259-05:00In practice, it is evident that computational com...In practice, it is evident that computational complexity is a part of mathematics.<br />The most fundamental question of complexity theory is that of separating the polynomial hierarchy. This is a mathematical question without any doubt.<br /><br />Also, in practice, mainstream complexity theory is driven by new mathematical ideas and techniques, coming from mathematicians. E.g, unique game conjecture is a purely mathematical problem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58285670069561202012010-05-08T08:00:00.138-05:002010-05-08T08:00:00.138-05:00Lance says: "Pure math is the study of abstra...Lance says: <i>"Pure math is the study of abstract objects, applied math develops tools used in other disciplines. Computational complexity is neither, rather an attempt to understand fundamental processes that occur in the universe, much like other sciences."</i><br /><br />This dovetails nicely with Mac Lance's <i>"Mechanics developed by the treatment of many specific problems"</i> ... if we make the following definition: "Complexity theory is the study of dynamics in all its forms."<br /><br />From this point-of-view, a Turing Machine is simply a general dynamical process over a Boolean state-space ... simulation is the pullback of dynamical processes onto simpler dynamical processes .. and the Church-Turing thesis is simply the statement "All theorems about computational complexity are theorems about dynamical processes ... and <i>vice versa</i>."John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19590215126991841612010-05-07T15:58:22.701-05:002010-05-07T15:58:22.701-05:00Anonymous says: When RAM became cheap enough that ...Anonymous says: <i>When RAM became cheap enough that DFAs were no longer common TCSers massively migrated away from the study of DFAs and into the study of the polynomial hierarchy.</i><br /><br />You have cited a good example of a complexity theory "selective sweep."<br /><br />But the particular sweep wasn't driven by RAM-induced technological obsolescence ... `cuz heck, finite-state machines are ubiquitous in mechatronic engineering even today (our own quantum spin microscope has several finite state machines embedded in it; we use them to shuttle molecules in-and-out).<br /><br />Instead the sweep was driven by precisely the mechanism that PWZ describe in <i>A=B</i>: "Algorithms that generate proofs constitutes some of the most important mathematics being done. The all-purpose proof machine may be dead, but tightly targeted machines are thriving"<br /><br />Thus, DFA as an complexity-theoretic discipline fell dormant because of the spread of tightly-targeted "proof machines" of the type that PWZ describe—a.k.a. "MATLAB StateFlow Toolboxes".<br /><br />More broadly, enterprises like CASP9 represent a continuation of the sweeping trend to encompass ever-larger state-spaces—both classical and quantum—within the domain of ever-more-sophisticated "proof machines" that generate validated and verified dynamical simulations.<br /><br />To borrow Knuth's phrase, what once we calculated by art (namely, our mathematical and physical intuition) we now increasingly simulate by science. <br /><br />These ongoing developments all rest upon natural foundations in complexity theory ... which (IMHO) is thus becoming *the* central discipline of every college of engineering.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68326298488085611892010-05-07T15:07:53.397-05:002010-05-07T15:07:53.397-05:00experimenting in social sciences:
http://www.ted.c...experimenting in social sciences:<br />http://www.ted.com/talks/esther_duflo_social_experiments_to_fight_poverty.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10351582435861743952010-05-07T14:13:56.460-05:002010-05-07T14:13:56.460-05:00We don't need to observe the universe to deduc...<i>We don't need to observe the universe to deduce anything about Complexity theory.</i><br /><br />We need to observe the universe to certify that what we are deducing is relevant to the real world. <br /><br />Some people might not care about applicability of CC and those are welcome to transfer to a math department. That is a property of them as researchers, not of the field as defined within CS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55548767713366421612010-05-07T14:10:43.112-05:002010-05-07T14:10:43.112-05:00We don't do experiments
Oh no, not the exper...<i>We don't do experiments </i><br /><br />Oh no, not the experiments == science argument again.<br /><br />By that measure astronomy isn't a science.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67072779623885564052010-05-07T14:09:31.105-05:002010-05-07T14:09:31.105-05:00Complexity theory is math. Saying that it is scien...<i>Complexity theory is math. Saying that it is science because we use models of computation that attempt to model the real world is like saying that Riemannian geometry is science because it models the real world (assuming our current theories of relativity). </i><br /><br />The analogy doesn't hold. Geometers wouldn't care if Riemann geometry is not the model of reality, whereas computer scientists would. In fact it has already happened. When RAM became cheap enough that DFAs were no longer common TCSers massively migrated away from the study of DFAs and into the study of the polynomial hierarchy.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45810941782155626952010-05-07T13:59:46.715-05:002010-05-07T13:59:46.715-05:00Randal Bryant's "Graph-Based Algorithms f...Randal Bryant's "Graph-Based Algorithms for Boolean Function Manipulation" contains a section titled "Experimental Results." Does this mean it's not a theory paper?<br /><br />I'll answer my own (not really rhetorical) question, by saying that I've seen plenty of theory papers that also discuss experimental results. (Bryant's just happens to have generated more citations than most.) Beyond that, there's an entire journal dedicated to "experimental mathematics." You bet pure mathematicians run -- and are informed by -- experiments about the "laws of numerical nature." Just because we can state all the rules of a model, it does not mean we understand the behavior of the model (unless lots of unlikely collapses really do occur).<br /><br />This isn't limited to the modern era of superfast desktop computers and GIMPS-type internet math projects. The interplay between mathematical experiment and mathematical proof goes back to the Pythagoreans.<br /><br />I see computational complexity, and TCS, as mathematical sciences.Aaron Sterlingnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74292446055011608152010-05-07T13:56:29.234-05:002010-05-07T13:56:29.234-05:00Anonymous says: Simulations don't count as exp...Anonymous says: <i>Simulations don't count as experiments, btw.</i><br /><br />LOL ... this statement reminds me of a STEAM reference I forgot ... this year's <a href="http://predictioncenter.org/casp9/" rel="nofollow">CASP9 Experiment</a> (a site well worth visiting for any complexity theorist).<br /><br />In CASP9 we get to watch a STEAM selection sweep vigorously in-progress ... because the (mainly young) CASP9 experimenters are putting into practice radically new ideas for the future of STEAM.<br /><br />These young CASP competitors *definitely* would not agree with assertions that "simulations don't count as experiments", because within the world of CASP, researchers routinely run tens of thousands of (fast, cheap, uncertain) computational experiments, for every one (slow, expensive, uncertain) wet-bench experiment.<br /><br />Now, which kind of experiment---physical or computational---yields gold-standard STEAM truths? In practice, both physical or computational experiments yield similarly fuzzy results ... and thus play similarly necessary roles ... such that neither can be wholly dispensed-with.<br /><br />From a computational complexity point-of-view, we are (apparently) still very far from approaching the algorithmic limits to CASP-type simulation capabilities ... which is terrifically exciting for everyone involved.<br /><br />Note: because I regularly attend the weekly research meeting of a of CASP competitor group, the above remarks direct observation of an in-progress STEAM selection sweep.<br /><br />The intent of the above is not to argue that CASP9 reflects how STEAM <i>should</i> work, but rather to observe, that experiments like CASP9 are increasingly how 21st century STEAM <i>does</i> (vigorously!) work.John Sidleshttp://www.mrfm.orgnoreply@blogger.com