tag:blogger.com,1999:blog-3722233.post111995741199840232..comments2021-06-13T17:50:43.943-05:00Comments on Computational Complexity: Defining TheoryLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger22125tag:blogger.com,1999:blog-3722233.post-1120097287168035472005-06-29T21:08:00.000-05:002005-06-29T21:08:00.000-05:00I tend to think of theory as an approach or method...I tend to think of theory as an approach or method more than a laundry list. That being said, a lot of the programming languages work (even denotational semantics) does not feel like "canonical theory." This may be a US-specific perspective. <BR/><BR/>Aside from a laundry list, you could always try for "theory is what graduate students taking prelims in theory have to study." Depending on where you are, though, that may be wildly different...<BR/><BR/>-David MolnarAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1120070382646985252005-06-29T13:39:00.000-05:002005-06-29T13:39:00.000-05:00So computer science isn't really a scienceThat qui...<I>So computer science isn't really a science</I><BR/><BR/>That quip was funny twenty years ago. Today anyone who doubts that informatics (aka CS) is a science only displays its ignorance of the field.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1120067596514170002005-06-29T12:53:00.000-05:002005-06-29T12:53:00.000-05:00There is a point of view that says that any subjec...There is a point of view that says that any subject that has "science" in it, isn't really a science. Look for instance at <BR/>"social science" or "political science". <BR/>Not really science, are they. On the other<BR/>hand, the pure sciences do not have "science" in them. <BR/><BR/>So computer science isn't really a science.<BR/>Thus, all this effort in defining "the theory of computer science" is futile :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1120058306859731132005-06-29T10:18:00.000-05:002005-06-29T10:18:00.000-05:00How about "the theory of computer science"? Serio...How about "the theory of computer science"? Seriously, the title is a pretty good definition, and most definitions suggested here are approaching that ultimate simplicity. If you want a definition of theory, you could say "the mathematics of computer science" instead.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1120048462287629582005-06-29T07:34:00.000-05:002005-06-29T07:34:00.000-05:001) I have real problems with the ubiquitous attemp...1) I have real problems with the ubiquitous attempt at pomo humor in the definition "an 'x' person is someone who is called an 'x' person and they do something called x". No one outside the system gets the humor or is helped in anyway towards understanding. <BR/><BR/>2) so what if the laundry list needs updating. math includes logic now but it didn't a hundred (er make that 150) years ago.<BR/><BR/>3) Pardon more negativity (and possibly inconsistency), but here goes anyway: I was really taken aback by the inclusion of programming semantics. Yes, it is mathematical, has lots to do with logic (and 'theory B'), lots of theorists do programming semantics relevant research, but as a subject area frankly does not fit well within my conception of 'Theory'. The main desiderata is that a person who they do 'programming semantics' will most likely teach .. hmmm.. programming languages or compilers, hardly ever automata or algorithms. Yes, there's lots of overlap (as with A.I.).<BR/><BR/>4) I now realise that whatever definition is chosen, it will almost surely include numerical analysis (or scientific computing) and they may or may not want to be considered on the same team.<BR/><BR/><BR/>MitchAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1120045264152160952005-06-29T06:41:00.000-05:002005-06-29T06:41:00.000-05:00How about: "TCS deals with the modeling and formal...How about: "TCS deals with the modeling and formal analysis of problems arising in computer science".<BR/><BR/>Yes, this is vague (since "computer science" is vague), but that's actually an advantage since now the definition of TCS encompasses more as CS encompasses more...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1120028559992746762005-06-29T02:02:00.000-05:002005-06-29T02:02:00.000-05:00In my opinion the definition of TCS should start w...In my opinion the definition of TCS should start with something like:<BR/><BR/>"TCS deals with the definition and analysis of mathematical models related to automized forms of computation and communication."<BR/><BR/>and then go on to give some examples (turing machines, interactive proofs, etc...).<BR/><BR/>-Zeev.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1120016937334094852005-06-28T22:48:00.000-05:002005-06-28T22:48:00.000-05:00p.s. - just to clarify - doing something in princi...p.s. - <BR/>just to clarify - doing something in principle does not always mean giving a polynomial-time algorithm to solve a computational problem on a Quantum Turing machine. <BR/><BR/>The "something" can be a computational problem, a cryptographic or distributed task, desiging a mechanism. Solving the something "in principle" means to do it in some interesting computational model (e.g., this can be a linear-time RAM machine). And of course, if we come up with the answer that something *can* be done in principle, then we should and do try to see if it can be done today with current technology.<BR/> <BR/><BR/>--BoazAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1120016269632053382005-06-28T22:37:00.000-05:002005-06-28T22:37:00.000-05:00No definition (whether laundry-list or not) will c...No definition (whether laundry-list or not) will capture all that we do. At the end of the day TCS is "defined" to be what people that call themselves theoretical computer scientists do.<BR/><BR/>That said, I can't resist giving another suggestion for a definition:<BR/><BR/>The mission of TCS is to understand the <I>principles</I> of computation.<BR/><BR/>That is, understand the power and limitations of computing devices (whether man-made or natural) <I>irrespective</I> of current technology.<BR/><BR/><BR/>The rational for this definition is that what distinguishes TCS is not necessarily the formal and mathematical tools, but the goal of understanding what can and can not be done <I>in principle</I>, rather what can be implemented on machines existing today or 5 years from now. <BR/><BR/>While mathematical methods are definitely our main <I>tools</I>, I prefer to give a definition using the <I>goal</I>. Indeed, experimental hueristics with no formal analysis can also be TCS work (if someone came up with such a heuristic that seems to solve SAT on all instances we find that would be a great TCS work). <BR/><BR/>Also, I believe that because at the heart of the matter we are more interested in what is true than in what is provable, as a community we are always quick to make assumptions and conjectures (which led to wonderful progress and results).<BR/><BR/>--Boaz<BR/><BR/>p.s. I think it would be nice if people signed their comments.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1120001951630093952005-06-28T18:39:00.000-05:002005-06-28T18:39:00.000-05:00why "efficient" computation? So, we don't study cl...why "efficient" computation? So, we don't study classes like EXP and NEXP because they are not efficient? or more precisely their problems with efficient solution are already captured by classes like P and NP? Removing the word "efficient" I agree with the definition.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1120000831749155442005-06-28T18:20:00.000-05:002005-06-28T18:20:00.000-05:00begin to define TCS: lance saz: "Theoretical Compu...begin to define TCS: lance saz: <I>"Theoretical Computer Science is the formal analysis of efficient computation"</I><BR/><BR/>an interesting analysis is always formal. plonk and redefine as <I>"Theoretical Computer Science is the analysis of efficient computation"</I> <BR/><BR/>of course, a computation of interest is always efficient. plonk and redefine as <I>"Theoretical Computer Science is the analysis of computation"</I> <BR/><BR/>of course, we analyse computation, not do it. plonk and redefine as <I>"Theoretical Computer Science is computation"</I><BR/><BR/>of course we study computation, not do it. plonk and redefine as <I>"Theoretical Computer Science is ... "</I><BR/><BR/>oh there is nothing in the definition!! let me add something to describe TCS. <I>"Theoretical Computer Science is having fun!"</I>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119988778391819922005-06-28T14:59:00.000-05:002005-06-28T14:59:00.000-05:00How about "TCS is the study of the foundational as...How about <BR/>"TCS is the study of <BR/>the foundational aspects of computation, information and<BR/>related mathematics".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119988334377284162005-06-28T14:52:00.000-05:002005-06-28T14:52:00.000-05:00I think the best so far is TCS is the formal analy...I think the best so far is <I>TCS is the formal analysis of computation.</I> You don't have to mention "modeling" because that's a prerequisite of "formal analysis". It does capture crypto since crypto is based on what can and can't be computed efficiently. It also captures design of algorithms, since "analysis of computation" can include not only what can be computed, but also <I>how</I> it can be done efficiently. It would also be OK to substitute "processing of information" for "computation"; these appear synonymous to me.<BR/><BR/>There still might be some missing areas: for example the question of whether one metric space embeds into another with constant distortion does not seem to involve any computation, although it might be answered using computational tools. But turning things around, I can't think of anything that falls under the above definition that <I>isn't</I> TCS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119977841434436992005-06-28T11:57:00.000-05:002005-06-28T11:57:00.000-05:00How about "Theoretical computer science develops a...How about "Theoretical computer science develops and applies mathematical methods for the systematic modeling, analysis, and solution of computational tasks"? This would take into account that theory covers not only 'internal' topics (as suggested by the "analysis of computation/information processing" definition), but is also sometimes applied to understand and develop tools for 'external' areas that have a computational character (such as e-commerce, comp. bio., networks etc.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119977304976444742005-06-28T11:48:00.000-05:002005-06-28T11:48:00.000-05:00Is the formal definition of the field so important...Is the formal definition of the field so important? If the main goal of a formal definition is to give the newcomer a taste<BR/>of what goes on in the field, then in my opinion, an example-oriented approach (more along the lines of the laundry-list definition) is more appropriate. <BR/><BR/>The laundry-list need not be comprehensive. Instead it is merely indicative of the kind of research that goes on in the field.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119974659691132672005-06-28T11:04:00.000-05:002005-06-28T11:04:00.000-05:00I don't think you can delete the "transmission of ...I don't think you can delete the "transmission of information" without substituting something else, because I don't see how "processing of information" covers, for example, crypto.<BR/><BR/>Transmission of information was meant to cover the fact that theory is about communication, which is not implied by just saying processing.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119973056656015082005-06-28T10:37:00.000-05:002005-06-28T10:37:00.000-05:00We lost the design there. Also the part of transmi...We lost the design there. Also the part of transmission we care about it is capture by processing So let's try that again:<BR/><BR/>"Theoretical computer science is the formal modeling, design and analysis of the processing of information."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119972366744653492005-06-28T10:26:00.000-05:002005-06-28T10:26:00.000-05:00But you are certainly not "designing" the informat...But you are certainly not "designing" the information, so the above is misleading.<BR/><BR/>My suggestion:<BR/><BR/>Theoretical computer science is the formal modeling and analysis of the processing and transmission of information.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119971167081490452005-06-28T10:06:00.000-05:002005-06-28T10:06:00.000-05:00How about the _design_ of algorithms or informatio...How about the _design_ of algorithms or information theory or kolmogorov complexity or crypto? Building upon the previous two, while still trying to avoid a laundry list:<BR/><BR/><BR/>"Theoretical Computer Science is the formal modeling, analysis and design of computation and information".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119968220626649162005-06-28T09:17:00.000-05:002005-06-28T09:17:00.000-05:00I don't have a better definition right now, but I ...I don't have a better definition right now, but I would point out that all the definitions suggested so far don't really capture most work in cryptography.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119960359336649032005-06-28T07:05:00.000-05:002005-06-28T07:05:00.000-05:00Lance's proposed definition excludes all that is d...Lance's proposed definition excludes all that is done in Theory B and possibly more. I suggest<BR/>"Theoretical Computer Science is mathematical modeling and analysis of computation."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119959602919735042005-06-28T06:53:00.000-05:002005-06-28T06:53:00.000-05:00I think that formal analysis of efficient computat...I think that formal analysis of efficient computation is more complexity theory than TCS as a whole and suggest the following alternative: <I>TCS is the formal analysis of computation.</I>Anonymousnoreply@blogger.com