not falling down

I guess I should finally talk about Websnark. I’m not a big fan of Websnark; I think Mr. Burns’s writing is self-important and sometimes really pretentious. He writes about webcomics the way college sophomores talk about politics. There are things about his style and tone–neither of which ever really drops from the surface–that really rub me the wrong way. And some of what he does is exactly what Checkerboard Nightmare, my favorite webcomic, has been doing for four years. But not as bitingly funny.

That said, he’s not a bad writer, and he knows what he’s talking about. He’s also managed to do what nobody else has done, which is establish himself as a guy who just blogs about webcomics every day, and people like it. Other people have tried to fill that niche, but Websnark is the first to really get tacit approval from the webcomics community in general. And he did it by just writing what he knew, and writing a lot, and spelling stuff right and everything. That isn’t nothing.

So I read Websnark, because everybody else reads it (even Sumana!), and because I like to read things by people with whom I disagree.

Now, I write an anacrusis every day, and I dislike applying the term “blog” to everything that’s written on the Interweb, and anyway I still want to think of myself as a webcomic artist. For those reasons, I privately think of Anacrusis as my current webcomic, because it’s more like a webcomic than anything else.

Mr. Burns has expressed before his belief that a comic well written is superior to a comic well drawn–that, in fact, the art in a comic is irrelevant if the writing is good (see Dinosaur Comics). So I’ve been tempted to email him and ask him to write about Anacrusis before; what would he make of a webcomic without any pictures at all? But I never did, because I have an intense distaste for self-promotion, among other reasons.

Then today he linked to Pulp Decameron, a “microfiction experiment” that doesn’t really qualify as microfiction under any definition I’ve heard, but whatever. It’s pretty good, if uneven as any daily fiction exercise, and I guess I know now how Mr. Burns reacts to a webcomic without pictures.

Okay, I’m done talking about Websnark now.

Theoretical problems in computer science are divided into classes based on their complexity. One class, called simply “P,” covers all problems requiring a yes-or-no answer that can be answered in polynomial time–which is to say that the amount of time needed to solve the problem is the result of substituting its input size for the variable in a polynomial equation. This is an important distinction, because that usually means it can be solved by a given deterministic computer (regardless of its speed) in some reasonable amount of time (ie before the universe ends).

There’s another class of problems, called “NP,” that has a special relationship with P. If a problem is in NP, there is no known algorithm for it that produces a solution in polynomial time–but the problem of verifying any given solution to the NP problem is in P. So you can figure out whether an answer is correct relatively quickly, but determining what the answer is could take a very long time. Longer than the sun has left in its life, for example, or longer than the universe has been in existence so far.

A final set of problems, called “NP-Complete,” is a special subset of NP. NP-Complete problems are very general and powerful–so general, in fact, that any NP problem can be transformed into an instance of any NP-Complete problem (and the transformation algorithm produces results in polynomial time). As you might imagine, these problems are very hard to solve, but of course their verification problems are in P.

If anybody ever produces an algorithm that will solve an NP-Complete problem in polynomial time, it will mean that all NP and NP-Complete problems are also solvable in polynomial time. NP and P will be equivalent sets. This would be a huge breakthrough in theoretical computer science, and it is likely that it will never happen.

But nobody’s proven that any NP-Complete problem isn’t in P, either. We only know that NP-Complete problems are not in P yet. (There’s a standing bounty on this; proof either way will get you a cool million bucks.)

As with most things that seem pointlessly theoretical at first, it’s not hard to apply the P-NP distinction to real life. It’s often easy to figure out that you’ve received an obfuscated message of some kind, whether it’s encrypted or noisified or divorced from its context. It may even be easy, given a possible meaning for the message, to decide whether that meaning applies. But deciphering the message from scratch can be very, very hard.

The difference between knowing that something is a message and knowing what the message means produces the best small mysteries.