'Twas brillig, and the slithy toves did gyre and gimble in the wabe

This took a little longer to write than I was hoping for. I did at least start typing before midnight...

While chatting with elemnar earlier we ended up discussing P versus NP (not quite sure how we ended up on that topic), and she came up with a surprisingly good analogy for it: proving P ≠ NP is like proving that there are no teapots orbiting Mars.

In a nutshell, P versus NP is about splitting problems in Computer Science into Easy and Hard problems. Problems in class P are Easy to solve, while problems in class NP are Hard to solve. Except we don't know for certain that NP problems are Hard because no-one's managed to come up with a proof for this. The best we've got is that we've only been able to find Hard algorithms for NP problems.

Note that this is very oversimplified. Some Hard problems are quite quick to solve in practice. Some Easy problems take ages to solve. Some Hard problems can be done in an Easy way to give a "good enough" answer for most purposes. But in general, Hard problems take longer than Easy problems and the difference becomes more significant as the problem becomes larger.

The general thinking in Computer Science is that P ≠ NP, i.e. there is a class of problems that will always be inherently Hard to solve. Indeed a large chunk of modern computing relies on this assumption.

Anyway, what has this got to do with teapots and Mars? Well, how do you know there isn't a teapot orbiting Mars? There aren't any giant teapots as someone would have spotted them by now, but all that gives is an upper bound on the potential size of any teapots (similar to how we've found various algorithms for NP problems and so have an upper bound on how Hard they are). No-one's come up with a formal proof for a presence or absence of a teapot, similar to how there's no formal proof either way for P versus NP. So all we know is no-one's seen a teapot, and there probably isn't one because it all makes much more sense that way... but there could be one out there somewhere that we've just not found yet. And P = NP might be true after all.

[Poll #2074983]

Today's discovery while randomly bouncing round TVTropes and Wikipedia is two truely mind-blowing things about Young's double slit experiment.

The first is that the experiment still holds true if you use individual electrons.

The second is that the experiment still holds true if you use larger particles. Like, for example, buckyballs.

Raymond Chen (of The Old New Thing blog) recently linked to a post asking, "How much does a gigabyte weigh?" The original poster had gotten confused (or is an excellent troll) and thought that as he installed stuff on his laptop it actually got heavier. Obviously that's not the case.

But it got me wondering. Does reading from or writing to something actually change the mass of it? See, if you apply a charge to something you do actually change the mass of it by a really tiny amount, as you're adding or removing electrons from the object. This probably means that flash memory will actually get heavier as you write to it, since it stores binary ones by trapping a charge on the chip.

I'm not sure if the same principle applies to hard disks (since they operate by storing a magnetic field rather than a charge), but nonetheless it's an interesting thought