tag:blogger.com,1999:blog-3722233.post113162983955300263..comments2024-06-13T23:23:44.643-05:00Comments on Computational Complexity: Favorite Theorems: Defining the FutureLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-1131735733615417732005-11-11T13:02:00.000-06:002005-11-11T13:02:00.000-06:00While Von Neumann deserves some credit for the ide...While Von Neumann deserves some credit for the idea of random access memory (and computability using random access memory), complexity is a separate matter and that was not properly formalized until Cook and Reckhow's RAM paper. (There were even competing notions such as storage modification machines at the time.)<BR/><BR/>(Von Neumann is probably better known for the notion of a stored program computer but from his letters to Turing it is clear that he drew this directly from Turing's universal machine.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1131728889166340772005-11-11T11:08:00.000-06:002005-11-11T11:08:00.000-06:00Didn't mean to disparage anyone's work; even Resol...Didn't mean to disparage anyone's work; even Resolution lower bounds are very interesting. My point ii) was speculative and slightly facetious, but I do think that in light of most researchers' feeling that fantastically new concepts are needed to prove P != NP, it's psychologically difficult (not to say methodologically invalid) to accept restrictions on theorem-proving that render even old concepts inaccessible <BR/>(in some cases, the first results of our field--Shannon circuit lower bounds--require exponential proofs). <BR/><BR/>This hard-to-swallow pill shouldn't be sugar-coated (though the power of the proof systems deserves to be noted, as in the cases N cites), in the same way that complexity research more generally shouldn't be (and needn't be) promoted by a false promise that P != NP is close at hand.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1131706303699943892005-11-11T04:51:00.000-06:002005-11-11T04:51:00.000-06:00The idea of a random access machine is usually att...The idea of a random access machine is usually attributed to von Neumann. Cook & Reckhow certainly knew this.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1131697194175727662005-11-11T02:19:00.000-06:002005-11-11T02:19:00.000-06:00Thankyou Lance.We were (and still are) waiting for...Thankyou Lance.<BR/>We were (and still are) waiting for your post on the latest proof of PCP theorem by Dinur.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1131692015212646892005-11-11T00:53:00.000-06:002005-11-11T00:53:00.000-06:00Why do results in proof complexity receive a coole...Why do results in proof complexity receive a cooler reception than results in circuit or communication complexity? <BR/><BR/>In a word, Frege systems. If you put a phrase "___ Frege system" in the title of your talk, you take a 30% hit in a attendance right there.<BR/><BR/>Seriously though, it probably comes down to applicability. People often get interested in new areas because the new area sheds light on some other questions that they had been thinking about before. Circuit complexity assumptions are often useful in cryptography or the study of complexity classes. Communication complexity has been a key tool for transferring from the computational realm to the combinatorial one, and thus getting results in many areas (such as circuit complexity, proof complexity, time space lower bounds etc).<BR/><BR/>Proof complexity, to the best of my knowledge (and dammit, I should know) has not found many applications for its results outside of the immediate sphere of logic and satisfiability algorithms. If you don't shed light on other folks's problems, then those other folks will go to the other parallel session or the coffee shop.<BR/><BR/>The notion that "limited logical systems seem intuitively unacceptable to the computer scientist" would be complete hogwash, but for the weasel-word "seem". The "toy systems" considered by contemporary propositional proof complexity are actually able to implement many interesting algorithms that people actually use for solving SAT or 0/1 LPs. For example, resolution for DPLL based SAT-solvers and cutting planes or Lovasz-Schrijver systems for 0/1 LPs. All the fancy clause learning based sat-solvers can be done with constant depth Frege systems.<BR/><BR/>NAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1131667758489410072005-11-10T18:09:00.000-06:002005-11-10T18:09:00.000-06:00The latter fields obtain decent bounds by restrict...The latter fields obtain decent bounds by restricting us to extra-simple toy models of computing. This seems intuitively acceptable, since I'm guessing many (most?) theorists have had a formative experience of been turned off somewhat from the operational complexity of real programming; further, they've been encouraged by results indicating that simple models like TMs are 'almost' as expressive as say RAMs--the spirit of computation flows undiminished here, and there's no upper bound on the conceptual complexity of algorithms.<BR/><BR/>Now, most theorists would I hazard not admit to having been traumatized by the mere logical form of mathematical arguments, such that they would take as a comfort the retreat to a toy model of *thinking* in which basic nonconstructive techniques like the Pigeonhole Principle become near-impossible to implement. Indeed, to prove the most difficult nonconstructive principles in math, PHP etc. had better be near-axiomatic, along with other concepts <BR/>currently beyond our ken.<BR/><BR/>In summary: <BR/>i) the simplifications in proof systems seem to lose too much;<BR/>ii) we're programming wusses but theorem-proving stallions by self-assessment, and putting on the analytical blinders of proof systems is hard to accept.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1131662576429790272005-11-10T16:42:00.000-06:002005-11-10T16:42:00.000-06:00Why does it seem (or am I wrong) that the receptio...Why does it seem (or am I wrong) that the reception of results in proof complexity is lukewarm compared to lower bounds in, say, circuit complexity, communication complexity, etc.?Anonymousnoreply@blogger.com