Older blog entries for Pseudonym (starting at number 10)

Creationism et al

mrorganic: Betcha didn't expect you'd start a minor religious bunfight (not really big enough to be a "flamewar" yet) on Advogato, didja? :-)

You ask:

How can any reasonably intelligent person believe in this trash?

Until relatively recently in history (couple of hundred years ago at the most), pretty much every intelligent person in the West did. So don't be so surprised.

The current theories about the age of the earth and the origins of life are not obvious. Neither is the theory that the Earth revolves around the Sun, to an Earth-bound observer. Quantum mechanics certainly isn't obvious. Sure, these things are scientific facts, but they're not obvious and they're not trivial. Therefore there are going to be reasonably intelligent people who dissent from the popular wisdom. You shouldn't be surprised.

As a theist, I strongly agree with you about the whole "hell" thing, though. I'm yet to work out why anyone thinks they'll persuade people to follow a religion with promises about what happens after death. Now, I admit it, I'm as morbid as the next person, but this is just Wrong(tm). The man himself put it best: "I came that they may have life, and have it abundantly." People who are in their chosen religion because of perceived or real threat of punishment after death are in it for the wrong reasons. They just Don't Get It(tm).

As a parting shot to this rant, I must echo the words of Dr Peter Carnley, who noted that "God did not send the Son into the world to condemn the world" (John 3:17), but His followers have more than made up for that omission.

Capabilities

dan: For an OS, you get capabilites from the kernel, or some appropriately delegated authority (which from hereon in I will describe as "a security service"). It's most certainly not "we haven't thought about it yet": there are many operating systems in use which use capabilities for security (EROS and Amoeba come to mind).

There is more to it, namely, how are capabilities implemented?

One method is to use unbreakable abstractions. Implement the capability inside kernel or security service, and your normal memory protection system should make the abstraction unbreakable.

The other option (used in Amoeba, because it's a distributed OS) is to use cryptography. It's slow. Enough said.

Mathematics

To the Advogato amateur mathematicians: For those interested in a more "open" MathWorld replacement, I've registered a project on SourceForge under the working title Principia Mathematica. The first mailing list, "principia-discuss" should be up in a little while. Please add yourself if you support the idea of an open encyclopaedic dictionary of the mathematical sciences.

There will be some interesting social and technical challenges. The most difficult technical challenge, as I see it, will be how to handle mathematical and diagrammatic content with a web-based interface in a form that's convenient for mathematicians. I have some thoughts on this (which involve converting between LaTeX, Lout and MathML amongst other things), but I'd like to talk about it first.

ahosey: Actually, 3 is not the smallest coefficient.

The number of decimal digits required to represent the positive number x is floor(log10(x)) + 1. The largest unsigned integer which is N bytes long is 256^N (actually it's 256^N-1, but 256^N always has the same number of digits as 256^N-1, since 256^N is never a power of 10).

It follows that the number of digits required to represent an unsigned integer of N bytes is floor(N * log10(256)) + 1. So the actual smallest factor is more like 2.408, but don't forget the addition of one.

schoen: Never heard of one of those. Incidentally, a resource that's not as good as MathWorld but can help sometimes is The Math Forum. Good luck.

Open question: Do we need a more "open" MathWorld? Perhaps a Wiki-like system?

schoen: Well done! Your proof is much neater than mine.

Now I believe we're well on the way to proving the full challenge. That is to prove:

HM <= GM <= AM <= RMS

Harmonic mean is N / (1/x1 + 1/x2 + ... + 1/xN). RMS is of course the root mean squared, not that other RMS. Equality holds if and only if all numbers in the multiset are equal.

There might be some other means which fit into the chain of inequalities. If anyone knows of them, please let us know.

Does anyone else think there would be much call for some kind of web log devoted to hobby/recreational mathematics?

Long time no blog.

mwh, schoen: The GM/AM inequality can be proven inductively, but it's not easy.

Basically, you prove it for the case N=2. Then you prove that if it's true for N, it's also true for 2N. Then you prove that if it's true for N>2, it's true for N-1. I can sketch out the proof if anyone cares enough.

If you haven't seen the Netizen wake photos yet, please do. I'm the one up the back with the baby on his head.

A question to C++-heads out there: Has anyone found a use for the STL built-in predicates, arithmetic function objects, binders, adapters and/or negaters? Note that I'm not asking "are they potentially useful?" I'm asking "has anyone actually found a non-contrived use for them on a "real" project?" I've been playing around with sequence algorithms for slinc and I keep finding that the built-in function and combinator objects are pretty much useless for any "real" task that I typically want to do. Is it just me?

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.

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...