tag:blogger.com,1999:blog-3722233.post4909167207073894023..comments2022-01-23T19:43:15.685-06:00Comments on Computational Complexity: Time Space Tradeoffs for SAT- good resuls but...Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3722233.post-46840116705907259252010-02-08T13:48:35.948-06:002010-02-08T13:48:35.948-06:00Before this, we did have TS = Omega(n^2) lower bou...<i>Before this, we did have TS = Omega(n^2) lower bounds, but it was a strange "internal state" of the field that we didn't know how to prove such a result for SAT.</i><br /><br />This is not really true. We only knew such things for multi-output problems where it is not fair to compare, not decision problems like SAT.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89786328998856248952010-02-06T14:05:57.657-06:002010-02-06T14:05:57.657-06:00Do you think that Rota would have co-authored with...Do you think that Rota would have co-authored with Erdoes .. if he had another chance ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48364271541765478762010-02-04T00:32:55.243-06:002010-02-04T00:32:55.243-06:00Even if your entire rant is correct, that doesn...<i>Even if your entire rant is correct, that doesn't mean the work was not worth doing. How are we supposed to know that a particular area fails to hold the Answer, unless some researchers explore the area? Intuition alone? Nobody's intuition has been good enough to get past the major barriers, so I think it's better to rely on concrete results than anybody's feelings about such matters.</i><br /><br />This. Mathematicians have pursued things which were intellectually satisfying for a long time, with little regard for immediate practical consequences. The end result of course is lots of stuff that's very useful. Sure, there's lots of stuff that's (so far) useless too, but I doubt anyone could have predicted which was which years ago. Maybe I'm being a bit to idealistic, but "What have you done for me lately?" is what business is for, not academia. (Nothing against business -- it's more effective and efficient than academia for a lot of things.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24857246017944079732010-02-03T22:51:34.407-06:002010-02-03T22:51:34.407-06:00I don't know much about CC so corrections are ...I don't know much about CC so corrections are welcome to the following. <br /><br />It seems to me that CC is not going anywhere right now. BNS stoped at log n, and generally I don't expect the discrepancy method to achieve much alone by RR (unless we get something crossing the barrier generally) as it can be approximated well in polytime (cf. AB last chapter).<br /><br />CC is a very interesting model, but it seems that we are facing the very same problem we had in circuit complexity with mod m gates, i.e. crossing log n degree/depth barrier. <br /><br />Finally, proving results in proof complexity has its own extra problems. AFAIK, we don't even have the lower-bound for the proof system corresponding to AC^0 with mod 2.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45895857955990179452010-02-03T18:35:53.417-06:002010-02-03T18:35:53.417-06:00the entire body of work in complexity theory resea...<i>the entire body of work in complexity theory research that mentions "Mod something", for something > 2, has been extremely unproductive.</i><br /><br />Even if your entire rant is correct, that doesn't mean the work was not worth doing. How are we supposed to know that a particular area fails to hold the Answer, unless some researchers explore the area? Intuition alone? Nobody's intuition has been good enough to get past the major barriers, so I think it's better to rely on concrete results than anybody's feelings about such matters.<br /><br />Besides, there's something weird going on with modulo, if you consider the work of Cai and others that has come out of Valiant's holographic algorithms. (Number of solutions mod "Mersenne" integers, for example.) Maybe not the notion of mod you meant, but you were wielding an awfully broad brush, so it was hard for me to know where your notion of mod ended. I certainly believe holographic algorithms/signature theory might tell us significant things about complexity that we don't already know.Aaron Sterlingnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81341393356255132282010-02-03T13:43:29.280-06:002010-02-03T13:43:29.280-06:00Mr. Gasarch, your conversation started going south...Mr. Gasarch, your conversation started going south the moment you said "Actually, he proved more than that..." and introduced Mod_k_SAT and things of that ilk.<br /><br />It is a cardinal mistake to assume that what we, within a narrow subfield of CS theory, driven by our internal logic, consider important and interesting is also important or interesting to science or society at large.<br /><br />A better response would be to delineate what we believe and what we know. For example, as far as I know, we don't know how to solve Graph s-t connectivity by an algorithm that runs in time O(n polylog(n)) and uses O(polylog(n)) space. A reasonable belief is that such an algorithm doesn't exist. Yet, we've just realized, thanks to Fortnow's result and its follow-ups, that the NP-Complete problem SAT doesn't admit such an algorithm. Before this, we did have TS = Omega(n^2) lower bounds, but it was a strange "internal state" of the field that we didn't know how to prove such a result for SAT.<br /><br />Ranting on a tangential note, in my humble opinion, the entire body of work in complexity theory research that mentions "Mod something", for something > 2, has been extremely unproductive. I sincerely believe that we tend to get carried away by the mathematical curiosity and some of the beautiful maths we can do, and forget the bigger picture. I will go out on a limb and say that the field would be no poorer without the (beautiful) results of Razborov and Smolensky on bounded-depth circuits with Mod gates. Similarly, complexity theory would've done just fine without all the follow-ups for Toda's theorem for various ModClasses and ModProblems.<br /><br />Another, not entirely dissimilar, red herring for the field is proof complexity. While motivated by an extremely important question (NP vs. co-NP), this field has been the analogue of "bounded-depth-circuit-complexity-with-Mod-gates" : the classes of "algorithms" for which lower bounds are proved are very specialized in nature, to the point that the proofs don't tell us less about proof complexity than about the artificial limitations of the models. Moreover, this field seems to be even less of a generator of new ideas, relying instead on transferring ideas from circuit complexity and other fields.<br /><br />A pity not enough people work on communication complexity: this is a field that takes the opposite view to circuit- and proof-complexity. Instead of crimping the model in highly artificial ways, it avoids looking at the minute details of the model, instead focusing on a very broad class of resources (bits exchanged). To me, there is greater hope that this field will connect better with the rest of mathematics (topology, information theory, etc.) and get us somewhere useful. From its inception, despite being a very "relaxed" model of resource consumption in computing, this field has shown itself to be rather useful and closely relevant to more pragmatic computational models such as VLSI, Sketching and Streaming algorithms.<br /><br />I might, of course, be entirely myopic and totally wrong, but I'd bet that none of the major complexity questions will be answered by techniques however remotely inspired by Mod-something (for something > 2).NP_Mod_P_Equals_CoNP_Mod_P_Equals_Zeronoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52256807925051731192010-02-03T13:42:54.959-06:002010-02-03T13:42:54.959-06:00Let's define "real people" to be &qu...Let's define "real people" to be "software engineers", since that is who was asking. (It's not the best possible definition, but whatever...)<br /><br />Of course "real people" do care about SAT; it is used in the real world all the time. There's a whole conference on it.<br /><br />Real people should also care about counting SAT assignments modulo a prime, since this (coupled with randomness and Valiant-Vazirani) would already be enough to do approximate model counting, which can be used to simulate different kinds of probabilistic reasoning with SAT. <br /><br />Linear time, tiny-space algorithms for these two problems would totally revolutionize applications. Why would "tiny-space" be nice? Because sometimes the instances you get from a reduction of your huge processor verification problem to SAT are so big, the instance can't fit in main memory all at once! The "tiny-space" requirement means you can still carry out the algorithm without running out of memory, without even holding the whole instance in memory at any given time.<br /><br />The time-space lower bound work shows that those algorithms just aren't out there.<br /><br />You don't like the results? Think they're too weak? Read the papers! Find the weaknesses! Prove something/anything better! Let's make the world of lower bounds a little less pathetic! Go, team!ryanwhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53710428790196841112010-02-03T13:34:08.543-06:002010-02-03T13:34:08.543-06:00Stating the result as something explicit about SAT...Stating the result as something explicit about SAT is technically stronger but obscures the larger context. The result immediately implies that NTIME(n) is not contained TIME-SPACE(n^d,n^c) for these suitable d,c even for a random-access TM (and indeed that is what is proved directly). <br /><br />The natural line of work that this relates to was that of Kannan (and Karp-Lipton) around 1978-1980. Interestingly, time-space tradeoff lower bounds were a focus of study at this time for non-uniform and structured computational models. The first strong general time-space tradeoff lower bounds were shown by Borodin-Cook for multi-output problems in 1980-82.<br /><br />I attribute the fact that these sorts of tradeoff lower bounds for SAT were not found until Fortnow developed the key technique in the late 1990's is the impact of Baker, Gill, Solovay's results on non-relativizing of P v NP. This meant that the sorts of TM reductions used in proofs of these results were unlikely to answer the big questions about the complexity of SAT, so a large part of the community shifted to the combinatorial methods for non-uniform computation. The focus of work in uniform computation after BGS and Karp-Lipton shifted to understanding connections to circuit complexity and randomization and hence to problems such as the NP-completeness of sparse sets considered by Mahaney et al and BPP in Sigma_2^P \cap Pi_2^P of Sipser et al.<br /><br />Lance made the point in the talks on his time-space tradeoff paper that people had over-reacted to the BGS result and as a result had dropped a potentially fruitful line of research. It is pretty clear to me that had his paper appeared in 1981 or 1982, it still would have been considered a major contribution.Paul Beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81180163261360774612010-02-03T13:13:33.511-06:002010-02-03T13:13:33.511-06:00also
s/resuls/results/also<br /><br />s/resuls/results/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61522522835763487382010-02-03T13:09:49.349-06:002010-02-03T13:09:49.349-06:00could give for there point of view
s/there/their/...could give for there point of view<br /><br />s/there/their/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84368649783695457012010-02-03T12:53:07.010-06:002010-02-03T12:53:07.010-06:00Deskin Miller-
Thanks- I fixed it.Deskin Miller-<br /><br />Thanks- I fixed it.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45113757571604658812010-02-03T12:33:23.539-06:002010-02-03T12:33:23.539-06:00If for nothing else, these lower bounds are good f...If for nothing else, these lower bounds are good for humor purposes.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19674732427880910752010-02-03T12:14:35.071-06:002010-02-03T12:14:35.071-06:00One minor typo I believe:
BILL: "...finding ...One minor typo I believe:<br /><br />BILL: "...finding the number of satisfying assignments mod p requires O(n^1.801) *space* if you insist on O(n^o(1)) space."<br /><br />I think the first 'space' is supposed to be 'time'.Deskin Millerhttp://twitter.com/deskinnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5019270940265407312010-02-03T11:02:59.741-06:002010-02-03T11:02:59.741-06:00@Gian-Carlo, your arrogant attitude hasn't cha...@Gian-Carlo, your arrogant attitude hasn't changed, has it ? All these years, you were striving to imitate me. <br />By the way, I was the one introducing you to the notion of lower bounds, remember ?Stanislaw Ulamnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6274901252795749252010-02-03T10:59:53.225-06:002010-02-03T10:59:53.225-06:00Well, I think Paul is right. Your comment is makin...Well, I think Paul is right. Your comment is making me thirsty. I haven't had my Coca-Cola for quite some time. <br /><br />Paul, I regret never having co-authored with you u. If you do get up, make sure to wake me up to ... I'd like to rectify my Erdoes number.Gian-Carlo Rotanoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72373527937899858282010-02-03T10:56:30.332-06:002010-02-03T10:56:30.332-06:00Don't make me turn around in my grave. I'v...Don't make me turn around in my grave. I've been sleeping well all these years. But ur ignorance makes me wanna wake up an slap u.Paul Erdoesnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85976549062343749322010-02-03T10:54:35.007-06:002010-02-03T10:54:35.007-06:00i dont even understand lowerbounds.i dont even understand lowerbounds.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45622357354623006332010-02-03T10:43:11.615-06:002010-02-03T10:43:11.615-06:00I think the overall point is that the progress in ...I think the overall point is that the progress in lower bounds has been extremely pathetic by any measure.<br /><br />(Almost) 40 years of research into NP-Completeness and we can't prove that solving SAT needs super-linear time.<br /><br />This is bound to shock students when they learn it for the first time.Anonymousnoreply@blogger.com