Older blog entries for Pseudonym (starting at number 3)

harrisj: I've seen several academic sorts assert that quantum computers will not help with cracking EXPTIME-hard problems, but I haven't seen a proof. Intuitively, they almost certainly won't help with EXPSPACE-hard problems, especially if it turns out that that EXPSPACE != EXPTIME.

schoen: Factoring is known to be in NP. Proof: Nondeterministically generating two factors is in NP, multiplying them together is in P, testing the result to see if it's the same as the number that you want to factor is in P. Therefore prime factoring is in NP.

We don't know if prime factoring is NP-hard (and therefore NP-complete), but the consensus is that it probably isn't. We also don't know if it's in P, but we know factoring algorithms that are tantalisingly close to polynomial. Something like O(n * log log n).

What makes these complexity classes particularly interesting is that we know the following relationships (where <= is the subset operator and < is the proper subset operator):


So at least one of the subset relationships in the chain above is actually a proper subset relationship. But which one(s)? Proving that P = NP will simply push tractibility up one step; the next interesting question would be if P = PSPACE.

If someone wants an interesting thought experiment, come up with a zero knowledge proof system or public key cryptosystem where breaking it is provably EXPTIME-hard, and thus provably hard to break. (As opposed to discrete log systems like ElGamal and RSA, which are only "probably" hard to break.) Then show the results to your local CS professor to receive your PhD.

15 Sep 2000 (updated 15 Sep 2000 at 04:06 UTC) »
Is there something you can take for Olympic fever?

I used to think the Olympics were something that were great if you liked sport. I'm not much of a fan, but I figured "more power to you if you enjoy it". A couple of months ago, however, when the torch relay hit our great land, I heard things that seemed out of place. Crowds were screaming, officials did everything but salute, people were even holding out their babies to touch the Olympic torch as it went past.

Does anyone else find this just a tad scary? Did the Olympics turn into a cult while I wasn't looking, or has it always been thus?

Well, the Olympics mean two good things at least: uni holidays for the next two weeks (students get in the way of the smooth running of a College) and good films on the other TV channels as they try to win back at least some ratings. Roll on, Olympics...

A few diary entries ago, Skud asked what was so "extreme" about XP. This is a partial answer to that question. I'm putting it here and making it more general because others might be interested.

This was useful for me because I've been interested in software development theory for a long time now, despite not having formally studied software engineering apart from one ill-fated semester which constituted my lowest mark in my computer science degree. Putting things into words makes you see just how much you understand (or don't understand, as the case may be) something.

Extreme Programming is a bit like design patterns, refactoring, programming on purpose, or Unix for that matter. It seems so much like common sense. However, there are two realities at work here.

The first is Henry Spencer's principle:

Those who do not understand Unix are condemned to reinvent it, poorly.

The principle extends to a lot of things beside Unix. In general, good practice requires good theory. If we don't have a good reason to do something, we might as well be doing something else instead. Software engineering is no different. From the point of view of the developer, IMO the most important legacy of The Cathedral and the Bazaar is that it tried to explain for the first time why bazaar development works. Once we know that, we can decide what bits are important, what bits aren't important and what experimentation might be fruitful. XP is no different. It may look like common sense, but in reality, it ain't so common. We need to understand it so that we aren't condemned to reinvent common sense, poorly.

The second reality is that medium- and large-scale software development in the Real World(tm) of deadlines and budgets requires justification to those who hold the schedules and the purse strings. Giving common sense a name and a series of papers and books makes it easier to justify to the PHBs. This goes doubly for the quality accreditation world (e.g. ISO 9000 and its relatives), where it's not so important what big-M Methodology you use, but the fact that that you use one at all. It puts you that one crucial step above ad hoc in the eyes of the professional world.

So why is it Extreme? It's extreme because it carries principles which are well-known and considered common-sense in the formal software development world and takes them to extremes. XP literature often admits that they may appear almost too simple. Well, they are simple. They are, however, implemented to extremes.

Let's look at a few examples.

  • We all know that design is a good thing. We've been taught that good design includes doing a big design up front so that the code falls out naturally. XP teaches that design is so good that we should do it all the time. Only when you have working code can you truly tell how it should be internally structured. The principle is called Refactor Mercilessly.
  • We all know that code reviews are a good thing. We've been taught that you should get someone else to look over your code before it gets checked in. XP teaches that code reviews are so good that we should do it all the time. In fact, programmers should work together. This principle is called Pair Programming.
  • We know that talking to the customer is a good thing. XP teaches that it's so good that we should get a customer to sit with the development team throughout the course of the project. This principle is called Onsite Customer.
  • We know that adding people to a late project makes it later. This is one of Brooks' laws from The Mythical Man Month. XP teaches that adding time to a programmer's week makes the project later too. XP defines OverTime as the time spent working that makes a programmer less productive in the long term. OverTime is banned in XP.

We in the open source community know a lot of this already, even if we can't articulate it. XP comprises a lot of bazaar principles such as Collective Code Ownership, Continuous Integration and Frequent Releases. But there are other principles, such as Pair Programming and Onsite Customer, which rely on proximity of developers and customers. While bazaar developers probably can't make use of these, open source companies should read and learn.

As always, this is IMHO and YMMV, but I hope this helps answer the question.

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!