Older blog entries for Pseudonym (starting at number 4)

harrisj: Thanks for the bouquet. It's only because I happen to be good at remembering this esoteric excreta.

You mentioned verification in P-time, and I think it's worth exploring what that means. One technical definition of the class NP is:

NP is the class of decision problems (languages) L such that there is a polynomial time function f(x,c) where x is a string, c is another string whose size is polynomial in the size of x, and f(x, c)=True if and only if x is in L.
(taken from the comp.theory FAQ)

As an example, x might be a graph, c might be a path in that graph, and f(x, c) is the function "is c a Hamiltonian path in the graph x?"

There are at least three kinds of questions that you may want to ask about this problem, given x. They are:

  • Is x in L, that is, does there exist c such that f(x, c)=True? That question corresponds to "does the graph have a Hamiltonian cycle"? Or "is the number composite"? This is called a "decision problem", and is not necessarily verifiable in P (unless P=NP, of course), because verifying an answer is identical to finding the answer.
  • Given x, give me a c which proves that x is in L. This kind of problem is trivially certifiable in P, because all you need to do is take the certificate c and compute the value of f(x, c). This question corresponds to "find me a Hamiltonian cycle in this graph", or "find me factors of this number".
  • Given x, find me the certificate c which minimises (or maximises) some cost function cost(c). This is called an "NP optimisation problem", and corresponds to something like "find me the Hamiltonian cycle of minimal distance" (i.e. the travelling salesman problem). I don't know whether this kind of problem is certifiable in P or not. Could someone please let me know?

Now to EXPTIME. EXPTIME-hard problems are not certifiable in P-time if the certificate is polynomial in the size of the input. If they were, you could construct a nondeterministic polynomial algorithm to solve them. (Nondeterministically guess the certificate in NP time then test it in P time.) So I guess EXPTIME-hard public-key systems and zero-knowledge proof systema aren't feasable. Darn.

If the certificate were not polynomial in the size of the input, that might be a different matter. That is, certifying EXPTIME-hard problems might be polynomial in the size of the certificate. I'm not sure about that one.

EXPTIME-hard problems often turn up when dealing with logic and theorem proving (e.g. constraint systems, conditional logic) or formal languages and the machines which generate/recognise them (e.g. tree automata). Here are some example EXPTIME-complete problems:

  • Evaluation of datalog queries for single rule programs containing only a single clause.
  • For tree automata, the intersection problem (i.e. given two tree automata, is the intersection of their languages empty) and equivalence problem (do two given tree automata accept the same language)
  • Removing recursion from formulas in the mu calculus (i.e. given a recursive formula, give me a non-recursive equivalent if it exists)
  • Satisfiability for definite set constraints
  • Determining a winning strategy for chess generalised to an N*N board or go generalised to an N*N board. I'm not entirely sure how you generalise chess piece movement, but there you go.

And just for fun, here are a couple of NEXPTIME-complete problems:

  • Satisfiability for two-variable first-order logic.
  • Provability in first-order multiplicative additive linear logic

Naturally, NEXPTIME-complete problems are certifiable in EXPTIME.

Happy theory nerding.

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):

P <= NP <= PSPACE <= EXPTIME
P < EXPTIME

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!