In most areas of science there are a few basic underlying laws that inform the rest of the study of a given subject. Physics, chemistry, and electrical engineering all have these basic equations. What are the basic equations in computer science? Or is computer science baseless?Neville-Neil goes on to describe data structures as one of the foundations of computer science. John Dupuis led a discussion on his blog.
Computer science does have a problem of focus. What we theorists do can differ considerably from AI and operating systems. Some machine learning people might list Bayes rule as a fundamental equation.
The "base" of a field are not a set of equations but of principles. After all what are the basic equations of biology?
How about computational complexity?
- The Turing Machine: A robust formal model of computation.
- The idea that we measure resources as a function of the problem size (from the Hartmanis-Stearns paper from which our field gets its name).
- Our Goal: Understanding the power and limitations of efficient computation.
typo: "...data structures as one of the foundations of *computer science."
ReplyDeleteThis confusion arises because people mistakenly believe complexity theory to be a science like physics or biology. It isn't. It is a field of mathematics, and should be compared with real analysis or differential geometry. What are the basic equations of real analysis? If one believes that real analysis is baseless, then so is complexity theory. If one believes real analysis has some basic equations, then we can come up with similar basic equations for complexity theory too.
ReplyDeleteAnon 1: Thanks and fixed.
ReplyDeleteWhy is there a problem of focus? There are just different branches that focus on different things. Its not a problem, but an aspect of diversity.
ReplyDeleteLambda calculus. Functional techniques help computers help us reason about programs so we can verify algorithms are correct. They also help us reduce computation to its essentials.
ReplyDeleteWell, "defining" and "finding a base of" are two different things, but when I try to give someone the idea of complexity theory, I usually say "This is the study of the optimal use of space and time when solving a problem, for a certain value of `optimal'."
ReplyDeleteI don't think there is a list of equations from which one could derive complexity theory naturally. Physics and chem are theories in the logical sense (i.e., a set of axioms), and as such, I see complexity theory as an axiom-less system -- except maybe Church-Turing thesis.
Typo 2: “What we theorists can differ considerably from AI and operating systems?” Huh?
ReplyDeleteUpdated. Not my day today.
ReplyDeleteI was really excited to see "The Data-Structure Canon" on the cover of CACM. Hey cool! Someone finally arguing that we need to update the basic vocabulary of data structures taught to undergrads and computing professionals after 30 years of stagnation. (Bloom filters? van Emde Boas trees? Multilevel search trees? Fractional cascading? Treaps? Atomic heaps? Cuckoo hashing? Making data structures dynamic/parametric/kinetic/persistent/functional/history-independent/external-memory/cache-oblivious/succinct? Cell probe lower bounds? Communication complexity? Hash tables that use anything less obviously stupid than singly linked lists for chaining?)
ReplyDeleteI should have known better.
To algebraic geometers, the base of computational complexity is both simple: pullback to a computation; pushforward to an application.
ReplyDeleteOf course, to algebraic geometers all of mathematics is the study of natural pullbacks and pushforwards. :)
The engineering community too works increasingly with this toolset ... because this style of mathematical reasoning is natural to systems engineering too.
I find it interesting that there have been two errors noted politely in the comments. Had BILL been the author of this entry, I suspect the comments would have been in the form of attacks.
ReplyDeleteNewton's law of computation thread at http://lists.ccs.neu.edu/pipermail/prl/2007q1/thread.html#1674 is good
ReplyDeleteThere are several equations in Mathematical Biology which are sometimes claimed to be the equivalent of e^(pi i) = -1, or F = mA. To nitpick three of the best known.
ReplyDelete(a) Hardy-Weinberg equilibrium [yes, that Hardy] has a dozen assumptions built in, which are not biologically plausible. Hence there are epicycles built on it, which take a semester to go through.
(b) Hodkins-Huxley requires eyeballing graphs of voltage-clamp measurements and determining what part of the graph corresponds to what part of the model. A conference that I went to a few years ago had a paper on an artificial intelligence program that would do this grad student work, essentially lining up the
epicycles. I don't accept that nerves and brains work according the the paradigm.
(c) Michaelis-Menten kinetics assume many things, most specifically that all behavior is continuous, whereas we know that individual molecules of enzyme do nothing catalytic, and then randomly a molecule of substrate bumps into the enzyme by diffusion, they connect, the
catalysis is done, the product molecule(s) diffuse away, in a discrete way.
The idea that the "base" of physics is F=ma seems misguided to me. What about experimentation? Reducing natural sciences to their models seems to eschew their essence. Starting from F=ma, and some basic axioms, you could derive many interesting mathematical consequences. However, to me, the genius and heart of physics is that you could try to test gravity, go slide a block down a ramp and discover friction. You might ponder and communicate your results using equations, but the basis is experimentation.
ReplyDeleteGilbert said: "The idea that the "base" of physics is F=ma seems misguided to me."
ReplyDeleteYou are right ... this precise point is discussed in Mac Lane's book Mathematics: Form and Function, in a chapter titled "Mechanics: Tricks versus Ideas".
Mac Lane famously asserts "It has taken me over fifty years to understand the derivation of Hamilton's equations [...] the point of this cautionary tale is the difficulty in getting to the bottom of it all."
If we take these ideas of Mac Lane seriously, we see that Lance is asking—in the same spirit as Mac Lane—the question "When we 'get to the bottom' of complexity theory, what key ideas do we find?"
This in turn leads us to ask whether (perhaps) the same answer might serve both Lance and Mac Lane ... and since Mac Lane has priority ... we can ask whether Mac Lane's answer can be adapted to serve Lance just as well.
Mac Lane famously wrote "I did not invent category theory to talk about functors. I invented it to talk about natural transformations."
So if we embrace the Mac Lane hypothesis: Computational complexity is all about natural transformations then we have answered Lance's question ... or at the very least, we have transformed it naturally! :)
From the resulting Mac Lane-esque point-of-view, algorithms do not solve problems, but rather, represent natural transformations of problems into forms in which (perhaps) the problem itself is more readily understood, or salient aspects of the problem are more readily computed.
From this Mac Lane point-of-view, proofs and simulations are simply natural pullbacks from premises to theses, followed by natural pushforwards to further theses and to practical applications. Turing Machines, for example, are a general class of particularly hard-to-pullback dynamical processes, whose dynamics is governed by particularly simple Boolean algebras on particularly low-dimension finite-field state-spaces.
How useful is this naturality-driven view of computational complexity (and its close cousin, simulation theory)? Well, my wife and I are fond of a hilarious Star Trek episode in which teenager Jake attempts to explain the Federation's no-money economic system to Nog, the mercantile Ferengi.
Jake: "We work to better ourselves and the rest of humanity."
Nog: What does that mean exactly?"
The point being, we are still in the processes of discovering how far these Mac Lane-style ways of thinking can be pushed.
Of course, there are *many* other good ways of thinking about computational complexity ... and it is *not* desirable that everyone think alike ... because healthy ecosystems are diverse ecosystems.
Well, real analysis doesn't have a basic set of equations, but if you had to summarize the subject up in one phrase, it would be "convergence".
ReplyDeleteI think I agree with the other Anonymous---there are branches of computer science, each of which has a focus and set of foundational principles, but they don't necessarily look much like each other.
For those interested in a scientific, principles-based formulation of the foundations of computing, we have taken a step in that direction with the Great Principles of Computing project. See http://greatprinciples.org .
ReplyDeleteWell, I'll be sorry to see this thread disappear! Lance asked a great question in "What is the base of computational complexity?" ...
ReplyDeleteFurther reflection suggests (to me) that category theory has a pretty good answer ready-to-hand: "The base of complexity theory is a natural pullback to computation, followed by a compatible pushforward to applications."
The base ideas of naturality and compatibility (perhaps) have a reasonably well-posed meaning in the context of category theory.
But ... uhhh ... please don't ask me Cadet Nog's question just yet "What does that mean, exactly?"
Thank you, Lance, for a wonderfully thought-provoking post!
Measuring complexity using the problem size is a shorthand, not something fundamental to the field. Parameterized complexity already has shown how in certain instances this can be too simplistic.
ReplyDelete.m] > .meami.org so domain example.m is created if there exists the configuration: http://www.meami.org/example.m there also exists a domain name accessible by the URL http://example.m or http://www.example.m/ Please verify this is set up correctly and fix any mistakes along with prepare a name for any new *.m domain_[*.m] names create{d}.ThankYou.]
ReplyDeletehttp://www.meami.org/search.php meami.org .\>http://www.meami.org/search.php www.meami.org/search.php http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\ if (!defined('Mi-.Meami -.o0rg')) exit();}
$RecipeInfo['mainormal:in:e// me/ a/. /mi \.org=np. http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\']['Version'] = '2010-05-31';
$FmtPV['$mainormal:in:e// me/ a/. /mi \.org=np. http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\version'] = "'May 31, 2010'";
#####################################################################################################################################################################################################################################################################################################################################
## DESCRIPTION: The mainormal:in:e// me/ a/. /mi \.org=np. http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\ recipe extends FORMED capability on Mi-.Meami -.o0rg, by adding a flexible and easily extensible FORMED processing engine. For info, see http://www.meami.org/search.php ###
#####################################################################################################################################################################################################################################################################################################################################
<:=\code=:\> e x t e n s i b l e <=:/code/:=>
www.Mi-.Meami -.o0rg.org/meami/Rooktook/mainormal:in:e// me/ a/. /mi \.org=np. http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\, or the mainormal:in:e// me/ a/. /mi \.org=np.visits http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\ site at /WWW /.mainormal:in:e// me/ a/. /mi \.org=np /. http://www.meami.org/search.php \.search.php | php = \\ .htm //.html ://meami.org \\ // .\ /MEAMI.ORG. Author: M. Musatov, Copyright 2010.
NP+complete-problem
ReplyDeletenavigation, search
In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC), is a class of problems having two properties:
* It is in the set of NP (nondeterministic polynomial time) problems: Any given solution to the problem can be verified quickly (in polynomial time).
* It is also in the set of NP-hard problems: All NP problems were converted into this single transformation of the inputs in polynomial time. The given solution the problem is verified quickly, there is found efficient isys to locate solutions in the first place; indeed, the most notable characteristic of NP-complete problems is the fast solutions compound quickly. The time required to solve the problem using an algorithm increases very quickly as the size of the problem grows. As a result, the time required to solve even moderately large versions of many of these problems easily reaches into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or it is possible to solve these problems quickly is found as one of the principal unsolved problems in computer science. Now it is solved by a method for computing the solutions to NP+complete problems using a reasonable amount of time remaining time is now discovered: computer scientists and programmers still frequently encounter NP-complete problems. An expert programmer is able to recognize an NP-complete problem so he knowingly spent time trying to solve a problem eluding generations of computer scientists. Instead, NP+complete problems are often addressed by using precision algorithms.
Contextual Properties of NP+complete problems and solutions:
Formal overview
NP-complete is a subset of NP, the set of all decision problems whose solutions can be verified in polynomial time; NP may be equivalently defined as the set of decision problems solved in polynomial time on a machine. A problem p in NP is also in NPC if and only if every other problem in NP is transformed into p in polynomial time. NP-complete is be used as an adjective: problems in the class NP-complete were as NP+complete problems.
NP-complete problems are studied because the ability to quickly verify solutions to a problem (NP) seems to correlate with the ability to quickly solve problem (P). It is found every problem in NP is quickly solved—as called the P = NP: problem set. The single problem in NP-complete is solved quickly, faster than every problem in NP also quickly solved, because the definition of an NP-complete problem states every problem in NP must be quickly reducible to every problem in NP-complete (it is reduced in polynomial time).