Very big, very exciting news in the theoretical comp sci world today!
A group at HP research has published a proof that, if correct, shows that the classic problem of computational complexity has been solved, once and for all. It’s still far from certain that it’s correct. But it’s the most credible attempt that I’ve ever seen, and it’s getting some preliminary favorable feedback from big-names in complexity theory. In fact, one of the biggest names in complexity theory, Stephen Cook, has apparently said that it should be taken seriously. If Cook thinks it’s credible, then it’s damn-well credible. It might not be correct, but it’s not just crackpottery either.
For the non-CS folks out there, here’s my attempt to explain what the problem is, and what the solution means.
In my post yesterday, I briefly mentioned the problem with simulations
as a replacement for animal testing. But I’ve gotten a couple of self-righteous
emails from people criticizing that: they’ve all argued that given the
quantity of computational resources available to us today, of course
we can do all of our research using simulations. I’ll quote a typical example
from the one person who actually posted a comment along these lines:
This doesn’t in any way reduce the importance of informing people about
the alternatives to animal testing. It strikes me as odd that the author of
the blogpost is a computer scientist, yet seems uninformed about the fact,
that the most interesting alternatives to animal testing are coming from that
field. Simulation of very complex systems is around the corner, especially
since computing power is becoming cheaper all the time.
That said, I also do think it’s OK to voice opposition to animal testing,
because there *are* alternatives. People who ignore the alternatives seem to
have other issues going on, for example a sort of pleasure at the idea of
power over others – also nonhumans.
I’ll briefly comment on the obnoxious self-righteousness of this idiot.
They started off their comment with the suggestion that the people who are
harassing Dr. Ringach’s children aren’t really animal rights
protestors; they’re people paid by opponents of the AR movement in order to
discredit it. And then goes on to claim that anyone who doesn’t see the
obvious alternatives to animal testing really do it because they
get their rocks off torturing poor defenseless animals.
A couple of people pointed out that in my wednesday post about Go, I completely left out the concurrency stuff! That’s what I get for rushing the post – I managed to leave out one of the most interesting subjects! Go provides very strong support for communicating processes.
I haven’t done a lot of hacking with the concurrency stuff yet – so my impressions of it are still very preliminary. But my early impressions are very good.
In general, I try to keep the content of this blog away from my work. I don’t do
that because it would get me in trouble, but rather because I spend enough time on work, and blogging is my hobby. But sometimes there’s an overlap.
One thing that’s come up in a lot of conversations and a lot of emails it the idea of cloud computing. A lot of people are interested in it, but they’re not really sure of what it is, or what it means.
So what do we mean when we talk about “cloud computing”? What’s the cloud? How’s it different from good old-fashioned client/server computing?
I’m away on vacation this week, taking my kids to Disney World. Since I’m not likely to
have time to write while I’m away, I’m taking the opportunity to re-run an old classic series
of posts on numbers, which were first posted in the summer of 2006. These posts are mildly
Ω is my own personal favorite transcendental number. Ω isn’t really a specific number, but rather a family of related numbers with bizarre properties. It’s the one real transcendental number that I know of that comes from the theory of computation, that is important, and that expresses meaningful fundamental mathematical properties. It’s also deeply non-computable; meaning that not only is it non-computable, but even computing meta-information about it is non-computable. And yet, it’s almost computable. It’s just all around awfully cool.
Since people know I work for Google, I get lots of mail from folks with odd questions, or with complaints about some Google policy, or questions about the way that Google does some particular thing. Obviously, I can’t answer questions about Google. And even if I could, I wouldn’t. This isn’t a Google blog; this is my blog, which I write as a hobby in my free time.
But there are intersections between my work life and my hobby. And one of the ideas that underlies many of the questions that I receive, and which also
hits on my work, and my hobby. And that’s the idea of scale. Scale is computer-science talk for how things change as they get bigger. In particular, I’m talking about the scale of information; the amount of information that we use on a daily basis has increased dramatically, and the amount of dramatic, fundamental change that has resulted is both amazing, and amazingly unnoticed by most people.
I don’t have a lot of time to write; I’m having my fifth (I think) upper endoscopy done tomorrow, which means that the day’s going to be a wash; and Yom Kippur is thursday, and I need to cook, so between the personal crap and work, I’m not going to have much time for blogging. So I’m trying to make use of the time I have to write one short but (hopefully) interesting post.
One thing that I’ve mentioned in passing is the distinction between message confidentiality, and message integrity.
Confidentiality is most of what we’ve been talking about
so far. Confidentially provides a guarantee that when you send an encrypted message, no one but your intended recipient is able
to read the plaintext.
Integrity is something very different. Integrity guarantees
that if you send an encrypted message, there’s no way that the encrypted message could have been tampered with after you encrypted it, without the recipient knowing it.
Colored Petri Nets
The big step in Petri nets – the one that really takes them from a theoretical toy to a
serious tool used by protocol developers – is the extension to colored Petri nets (CPNs). Calling them “colored” is a bit of a misnomer; the original idea was to assign colors to tokens, and allow color-based expressions on the elements of the net. But study of analysis models quickly showed
that you could go much further than that without losing the basic analyzability properties
that are so valuable. In the full development of CPNs, you can associate essentially arbitrary
collections of data with Petri net tokens, so long as you use a strong type system, and keep
appropriate restrictions on the expressions used in the net. The colors thus become
data types, describing the types of data that can be carried by tokens, and the kinds of tokens that
can located in a place in the net.
So that’s the fundamental idea of CPNs: tokens have types, and each token type has some data value associated with it. Below the fold, we’ll look at how we do that,
and what it means.
Among many of the fascinating things that we computer scientists do with graphs
is use them as a visual representation of computing devices. There are many subtle problems that can come up in all sorts of contexts where being able to see what’s going on can make a huge difference. Graphs are, generally, the preferred metaphor for most computing tasks. For example, think of finite state machines, flowcharts, UML diagrams, etc.
One of the most interesting cases of this for one of the biggest programming problems today is visual representations of concurrency. Concurrent program is incredibly hard, and making a concurrency regime correct is a serious challenge – communicating that regime and its properties to another developer is even harder.
Which brings us to todays topic, Petri nets. Actually, I’m probably going to spend a couple of days writing about Petri nets, because they’re fun, and there are a lot of interesting variations. The use of Petri nets really isn’t just an academic exercise – they are seriously used by people in a lot of real, significant fields – for one example, they’re very commonly used to specify behaviors of network communication protocols.