I have no idea how to write emails

No, I don’t mean like writing a program that handles emails or even a regexp for checking whether an email address is valid. I certainly don’t know either of those and it wouldn’t be blogworthy to mention something that’s both true for most people and not expected of me.

I literally mean the composition of email messages.

You see, I was stuck in a not-quite-a-job for two years, a fairly large chunk of which I wasn’t working at all, and a fairly large chunk of the remaining actually-working bits was reading emails, and a small chunk of that remainder was writing emails. Which was still a considerable amount of emails compared to the quantity I sent throughout six years of high school (which was probably in the ballpark of 40 to 50 messages).

However, I had pretty much zero respect for the recipients of the messages I was composing. I don’t know how many of my rants regarding this topic survived my purge of embarrassing articles, but if you read my previous posts on the topic, you know what I mean. I’ve straight-out insulted people of vastly higher rank or standing in my messages. For that matter, there were requirements on how email messages were supposed to be formatted, but as far as I can tell there was exactly one (read: 1) office I communicated with which followed the guidelines, and they also happened to be located in HQ MINDEF so I guess it’d be pretty hypocritical if they didn’t follow their own guidelines. I don’t remember the arcane rituals one must follow in order to craft the electronic mail message of greatest dignity but I’m pretty sure I violated them with the very first word of almost every single message I sent because I addressed most people with this two-letter word: “Hi”. I also addressed most officers by their given name instead of surname, which probably also violates a dozen other protocols.

I mostly didn’t give a shit because I didn’t believe in authority. The funny thing about that job was that it was compulsory for almost every male of this country, and generally people let you get away with doing whatever because, firstly, they don’t want to further antagonise someone working in a job they don’t love and secondly, unless you’re really causing a lot of trouble for them with your nonsense, the red tape involved in official punishment is simply not worth it. I figured that that was part of how I managed to avoid punishment with my outright trolling messages.

I don’t have these excuses to fall back on now.

A couple of years ago—I don’t remember whether it was on this blog, the old blog, or Twitter, or wherever the heck I stashed away dumb ideas—I flippantly mentioned that email signatures like “Best regards,\n[my name]” are absolutely worthless if they’re automatically added, because then it just becomes a bunch of meaningless words you send with every message. I did use automatic email signatures during the job stint, except I forwent the “yours sincerely” bullshit and left actually useful information like my name and job scope. Now that I’m a student, I don’t exactly have a job scope so I assume I could just leave my name. Except that email messages have a name field, so I could just omit the signature altogether. Is this a good idea? I don’t know!

All I know is that the style of email writing I’d acquired in the last two years is probably not going to be suitable, and this might be a slight problem.

Orthonormal integer-translate partitions of unity

I was thinking about this for a bit.

What are the finite functions that satisfy the following three criteria?

\displaystyle\sup\,\{x\,|\,f(x)\ne0\}-\inf\,\{x\,|\,f(x)\ne0\}<\infty\quad\text{(finite support)}\\  \forall x\in\mathbb R\quad\sum_{n\in\mathbb Z}f(x+n)=1\quad\text{(partition of unity)}\\  \forall n\in\mathbb Z\quad\int_{\mathbb R}f(x)f(x+n)dx=[n=0]\quad\text{(orthonormality under integer translation)}

For instance, we have the boxcar function x\mapsto[-1/2<x<1/2].

And then I can’t really think of anything else. It seems somewhat nontrivial coming up with such functions with larger support. I’ve seen an example somewhere, so it ought to be possible, but I can’t remember it.

There’s also the uninteresting example of partitioning the unit interval [0,1] into a finite number of smaller intervals A_k,\,k\in\mathbb Z, whence the function x\mapsto[x-\lfloor x\rfloor\in A_{\lfloor x\rfloor}] is constructed. This allows arbitrarily large supports (as defined by the range) but also seems too much like a hack and isn’t quite what I’m looking for.

A “trivial” result is that if we assume that the support is an interval (open or closed doesn’t matter) and that the function is positive throughout said interval, then this interval must have length at most 1 (otherwise \int_{\mathbb R}f(x)f(x+1)dx>0) and therefore has to be the boxcar function or a translated version thereof.

On doge

I am (still) being awfully upset over the doge meme which exploded in popularity around the start of the year. This one internet fad has ruined the words “so”, “much” and “wow” for me.

Thankfully, like most memes, it died out after a while and I haven’t been seeing so much of it lately, though the damage has long since been done.

π/4

So, today is Pi Approximation Day, and unfortunately I have nothing very closely related to π to present today.

Anyway. Let’s have a look at the Rubik’s Cube. There are effectively six moves available, which we may take to be {U,D,L,R,F,B}, as usual. (It is, of course, possible to instead use {U,u,R,r,F,f} or {U,R,F,E,M,S} as a “basis” instead, but using the standard moves fixes the centre facelets.)

It is obvious that with a normal Rubik’s Cube, you’re only allowed to turn the faces in multiples of 90°, for the very simple fact that edge cubies and corner cubies are shaped differently and you can’t just interchange them.

But what if we could? What if we turn the faces by only 45°?

It’s probably not possible to make a good real implementation of this, since, projecting the cubies onto a sphere, edge cubies and corner cubies have different latitudes, so the turns will inevitably have some bumpiness. (The path of motion is also most likely forced to be nondifferentiable.) I presume using magnets would be the most straightforward way of creating this idea IRL, and this has probably already been attempted by puzzle-modding enthusiasts.

There is also the Mixup Cube, where faces are still restricted to 90° turns, but slices can turn by 45°; corners remain corners, but edge and centre cubies are now equals. This is conceptually similar to Mozaika and a few other puzzles, except that edge cubies on the Mixup Cube have orientation. (Depending on stickering, the centre cubies might not have visible orientation, in which case the Mixup Cube’s states don’t form a group.)

Getting back to the idea of a 45°-face-turn cube, centre cubies are still fixed and edge/corners can freely mix. It’s not hard to prove that arbitrary permutations (not just even permutations) can be obtained due to the existence of an eight-cycle. As on the usual Rubik’s Cube, there is an orientation invariant; if we choose an orientation reference as pointing towards the direction of increasing latitude, U/D don’t change the orientation, while any of the other four face turns changes the orientation of four pieces by 30° and the other four pieces by 60°, resulting in zero total orientation change.

The non-centre cubies have six possible orientations. On a normal Rubik’s Cube edge orientation corresponds to a cyclic group of order 2 and corner orientation corresponds to a cyclic group of order 3; since edges can corners can mix here, this means they should have at least six orientations. While it’s mentioned above that a non-horizontal face turn would change the orientation of four cubies by a twelfth of a revolution, it turns out that that’s just an artifact of how we decided to label our reference orientation. Any originally E-slice edge cubie in a non-E-slice position necessarily has orientation an odd multiple of 30°, and likewise for any originally non-E-slice cubie in an E slice position.

The centre cubies have eight orientations. Unlike the non-centre cubies, the total orientation is not an invariant in either the 45°-face-turn cube or the Rubik’s Cube. Instead, the parity of the total orientation equals the permutation parity of the non-centre cubies for the former. This can be seen to be because every turn changes both the permutation parity and the centre orientation parity. Like the Rubik’s Cube and unlike the Mixup Cube, ignoring the centre orientation still results in a group.

The 45°-face-turn cube would have a total of 20!\cdot6^{20}\approx8.9\cdot10^{33} states if centre orientation is entirely ignored, 20!\cdot6^{20}\cdot2^6/2\approx2.8\cdot10^{35} if the parity of the centre orientation is used, and 20!\cdot6^{20}\cdot8^6/2\approx1.2\cdot10^{39} if all eight orientations are distinguishable. That said, it’s not really the number of states which determines a puzzle’s difficulty—the Megaminx has many more states than a Rubik’s Cube but can be solved in pretty much the same way.

For that matter, the availability of a 45° face turn in our described puzzle would probably make it easier to solve than a normal Rubik’s Cube. At least the permutation aspect reduces into an almost-trivial puzzle that can be solved by spamming commutators/conjugates, after which the orientation could be solved with the same technique or the usual Rubik’s Cube algorithms. Using commutators is a particularly easy “first principles” way of solving puzzles that behave sufficiently like groups, but generally interesting puzzles don’t have simple commutators to exploit. Huge parts of my two gigaminx solves were done through conjugated commutator spam, for example, and considering that they both took more than an hour, this also highlights how incredibly inefficient solving with commutators/conjugates can be when they involve more than just a few moves. In this case, taking just two faces of the 45°-face-turn cube and ignoring orientation reduces to a (5,3,5) rotational puzzle, which is easy to solve with simple commutators.

Now, suppose we also add 45° turns to slices, like the Mixup Cube. This monstrosity can mix every cubie together and in all likelihood can never be manufactured. Every piece has 24 possible orientations and every permutation of the 26 cubies is possible. I’m not sure about what the orientation subgroup is like, but I guess there are either three or six orbits since each move changes the total orientation by a multiple of 45°. Assuming that there are three orbits and that the centre cubie orientations are distinguishable, this would have 26!\cdot24^{26}/3\approx1.2\cdot10^{60} positions.

Update: I borked the HTML which caused half the post to vanish when viewed from the front page. Also expanded on some stuff.

Something else

成績

試合数: 498
試合時間: 146.6 hrs

四人

試合数: 271
試合時間: 106.3 hrs

三人

試合数: 227
試合時間: 40.3 hrs

I’ve probably spent too much time playing on Tenhou. Also, as mentioned in the last post about mahjong, I dropped from 2dan to shodan in both four-player and three-player, though through some amazing amount of luck I managed to grind myself to 3dan in three-player. Three-player (with Tenhou’s rules) involves a lot of luck, anyway—a string of repeated dealerships can readily give one player a huge lead over the other two (this happens with greater frequency than in four-player simply because there are fewer players), and hand values are greatly inflated compared to four-player due to a larger proportion of tiles being yakuhai or dora and hon’itsu/chin’itsu being much easier to get. Yakuman and kazoe yakuman are also much more common; I got a kokushi musou and a suuankou tanki some time ago (along with a few more non-tanki suuankous and daisangens).

Anyway, I was thinking about this: suppose we generalise mahjong to a hand with arbitrarily many tiles (possibly restricted to 3n+2 as in normal mahjong); what is the computational complexity of determining whether a given hand can be interpreted as a group of melds and a pair? This doesn’t seem to be entirely trivial (figuring out the waits for single-suit hands with only 13/14 tiles still confuse me occasionally), but on the other hand it almost seems like it obviously should be in P.

I once again blog about how bad Windows is

Yesterday evening Two evenings ago I set the computer to sleep, with the battery about half full. My limited experience tells me the battery would theoretically take about two weeks to go from from fully charged to fully discharged when suspended, so just a day of suspension should be all right.

About an hour ago I switched it on, only to be greeted by “Resuming Windows”, which indicates that for some reason it decided to hibernate instead of sleep. Whatever, it’s not the first time this happened. Now, for some retarded reason I splurged on RAM upgrades (seriously what the hell do I need 16 GiB RAM for on a laptop) so hibernating takes some nontrivial amount of time, and so does resuming from it. But okay, whatever.

Then right after it finished starting up, Windows hurfed a durf about configuring updates and promptly—by which I mean without a prompt—restarted on its own.

Whatever.

Unrelatedly, I had the QET two days ago. I actually tried to do it seriously for a while before they announced that there was only fifteen minutes left on the test, at which point I just gave up because it’d’ve been impossible to finish the rest of what I had in mind with that little time. Guess I’ll have to take extra English modules.

RIP uptime

> 12:14:59 up 63 days, 18:52, 4 users, load average: 0.70, 0.61, 0.50

Guess I’ll take the old computer off the grid for a while.

Windows a shit, part 3

I just remembered I already wrote two posts on this topic, so I’m just going to call this part 3.

IE 11 does keep keyboard layout within a window consistent (IE 8 doesn’t)

J/k, it doesn’t. The location bar apparently keeps track of keyboard layout separately. Yes, that is as baffling as it sounds.

Anyway, I have a couple of things to say regarding package managers and Windows 7’s lack of an inbuilt one. Package managers are freakin’ awesome and make installing and updating things a lot less annoying. Instead, what I’m doing is I’m searching on Google for an executable to download (and 90% of the first page of results is inevitably shady) and then running the installer (quite often without “setup” or “install” in the name, because who needs to know whether that’s the installer or the program itself?), only to realise the retarded installer didn’t add the program to PATH (because having to type out the full path to a CLI tool every time is very user-friendly).

Speaking of PATH.

[screenshot: the Windows environment variable editor]

The “official” way of editing PATH is to open up this dialogue box and edit whatever is in that text field. Notice how it can’t display one full path from a typical Windows setup; it’s not even resizeable. Do I need to say any more regarding how dumb this is?

[screenshot: also the Windows environment variable editor]

Oh, and the dialogue from which the previous dialogue is launched is this one. It’s so long that it has a scrollbar, but you’re not allowed to use the scrollwheel on your mouse to scroll it. Every time I want to edit PATH (which is depressingly often) I have to use my mouse to drag the scrollbar. You know, that action that leads to a lot of jeering and mockery when people who know about scrollwheels see you doing that.

Now, about ramdisks. I tried ImDisk and it didn’t work. So now I’m using this “SoftPerfect RAM Disk” thing, which does work, but doesn’t exactly do what I want. Ideally the ramdisk shouldn’t actually be using RAM if it isn’t filled, but SoftPerfect RAM Disk allocates it all at once because it needs to be formatted as FAT/NTFS/something else Windows can read. (This also means that it takes a nontrivial amount of time to initialise if the ramdisk is a couple of gigabytes large.) By the way, Linux has inbuilt ramdisk support and treats the ramfs/tmpfs filesystem types as first-class citizens among other filesystem types. (Memory usage for ramfs/tmpfs is also dynamic, of course. Linux is actually sane.)

Because I had the brilliant idea of formatting both of my external hard disks as ext4, I can’t use them on Windows directly. So I plug them in to the old computer, set up win-sshfs on the new one, and access files over SSHFS like any sane person wouldn’t. This turns out to be awful for a couple of reasons. One, the router/modem SingTel provided is absolute horseshit and can’t handle speeds beyond around 6 to 7 megabits/second. Not even within the home network. Two, win-sshfs itself is not exactly the best software for SSHFS ever.

It has some documented quirks like not recognising symlinks, and that’s okay because at least those are documented. It also has some not-documented quirks like crashing if you happen to select multiple files and access them simultaneously at 4 o’clock on a Sunday afternoon. That, for example, is not okay. Furthermore, unlike the *nix SSHFS, it apparently doesn’t cache at all, so everything is always slow. (It has an approximately 14-second delay on opening previously-unaccessed files, but my experience with SSHFS on Linux hasn’t been much better. That said, said previous experience with SSHFS on Linux involved servers located in another continent, which contributed at least a little to the delay.)

Also, re: gdipp; I have that disabled now. I can’t stand the broken font rendering anymore. I mean, whatever Windows is doing is obviously also broken, but it’s less so. It’s 2014 already, why don’t we have 200 ppi displays on the desktop? Instead we get phones with absurdly and unnecessarily high resolutions.

Anyway, the last couple of paragraphs don’t really relate directly to Windows. One of the other things I was going to hurf durfs about (and forgot when I initially published this post) was that Windows does not provide workspaces, which is a common Linux DE feature I use a lot. Everything on the main workspace, IRC on a secondary workspace. Now, I usually use this Windows laptop with an external monitor attached. It turns out that the stand that came with the U2412M isn’t very tall at all so a dual-monitor setup would force me to look at the laptop monitor at a relatively extreme angle (which makes the colours look bad because the laptop monitor is TN) and that is already somewhat unpleasant to use. I did, however, experiment with it for a while.

My major gripe is that Windows does not, by default, use a colour scheme that allows easy differentiation of active and inactive windows. (I don’t know if this is related to the whole laptop-uses-TN-so-colours-all-look-like-junk thing, but hey.) So what ends up happening is that sometimes I’m looking at the wrong monitor and typing things into the wrong window. This is frustrating and basically a thing that shouldn’t be happening. In theory using two monitors should provide a better workflow than using two workspaces, but this turns out not to be the case with Windows. (Do people with multiple-monitor setups actually use multiple monitors concurrently? I find it hard to focus on what I’m doing if I have too many other things open.)

Untitled

Tomorrow I will stop procrastinating things and get the things I need to get done done.

Maybe.

We’ll see when the time comes.

(By “tomorrow” I naturally mean when I wake up, not literally tomorrow.)

Anyway, I have to go take this “Qualifying English Test” thing because I couldn’t be bothered with English classes in school before. I had a look at the sample question and the topic seemed awfully dreary. Failure is pretty much guaranteed at this point since I suck at writing (despite having produced over a thousand blog posts). Or maybe it’s that I suck at writing about things I don’t care about.

Yeah, let’s go with that.

Something about functional equations

\displaystyle f:\mathbb R\to\mathbb R\\  f(x)=f(1/x)\\  f(0)=0\\  f(1)=1\\  f'(0)=1\\  f(-x)=-f(x)

Assuming f is smooth, solve for f.

A nonsolution is f(x)=\exp(-(\log|x|)^2)=|x|^{-\log|x|} with the removable singularity at x=0 removed. It’s smooth, but f'(0)=0. (In fact, every derivative is zero at x=0.) Another nonsolution is f(x)=[|x|\le1]x+[|x|>1]/x, which satisfies every condition other than smoothness.

What I tried was to expand a Taylor series around x=1 then solve for the coefficients using only the constraint of f(x)=f(1/x), but this was fruitless. Let f(x)=\sum_{k\ge0}a_k(x-1)^k. Then:

a_1=0\\  a_2+a_3=0\\  a_3+2a_4+a_5=0\\  a_4+3a_5+3a_6+a_7=0\\  a_5+4a_6+6a_7+4a_8+a_9=0\\  \vdots

Any finite truncation of this list of equations would have more unknowns than equations and hence be unsolvable. From another point of view, this means that there are infinitely many degrees of freedom to exploit in order to make f satisfy all the other conditions, and I’m not sure what exactly to do here. (Incidentally, this led to the previous post about symmetric polynomials, where the relation to polynomials stem from treating the LHS as generating functions.)

One sort-of-obvious thing to note is that we somehow have to choose the coefficients such that they don’t grow too quickly, so we can have a nonzero radius of convergence. For instance, fixing a_k=0 for all even k\ge4 and a_2=1 the odd coefficients end up being:

a_3=-1\\  a_5=1\\  a_7=-3\\  a_9=17\\  a_{11}=-155\\  a_{13}=2073\\  \vdots

Which is A001469 which grows superexponentially and therefore has a zero radius of convergence. Nope, useless. On the other hand, fixing a_2=a_4=\cdots and a_3=a_5=\cdots and adding the oddness constraint results in a_2=1/2, which leads to f(x)=\frac12(x+x^{-1}), which has a pole at x=0. Durr.

Anything involving \log x is automatically unnice due to the singularity at x=0, even though converting it to a function of (\log x)^2 seems like the obvious course of action.

Update: Clearly any analytic function is not going to make the cut since it’d have to be symmetric in x and 1/x, so the function can be expressed as a Taylor series in terms of x+1/x, which necessarily causes a discontinuity at x=0. That said, explicitly constructing a function satisfying all the requirements is not difficult through the use of bump functions and the like; what I wanted was a simple function that can be defined without resorting to such hacks.

Something about symmetric polynomials

In the middle of researching something I discovered that (1+x)^{2n+1}-x^{2n+1} can be expressed as a polynomial in x(1+x) for certain small values of n. (This is reminiscent of and probably also related to Faulhaber’s formula and the Bernoulli numbers, incidentally.)

The very first thing to note is that this is not a symmetric formula in 1+x and x. On the other hand, it is symmetric in 1+x and -x, whence we may apply the fundamental theorem of symmetric polynomials which implies that (1+x)^{2n+1}-x^{2n+1} may be expressed in terms of (1+x)+(-x) and (1+x)(-x). Obviously, since the former term is just 1, this also means that (1+x)^{2n+1}-x^{2n+1} is a polynomial function of -x(1+x) and hence also of x(1+x).

I’m ashamed to admit that noticing this took me about an hour (interrupted by a shower, but still). The previous approach I had was—ugh—induction, which didn’t work out because I copied a sign wrongly somewhere. Having fixed that, a proof by induction is simple, and also suggests the more general statement that (1+x)^n+(-x)^n is a polynomial in x(1+x)… and this general statement makes the symmetry extremely obvious.

(Among other goofs I made today, I wrote 26 for 30−2 somewhere. That was dumb, and what made it even dumber was how long it took me for notice. I might be getting just slightly out of touch with basic arithmetic.)

TANOSHII

[screenshot: daisangen]

[screenshot: suuankou]

Of the three main yakuman hands the only one I haven’t gotten yet is kokushi, which I’ve been in tenpai for exactly once. That said, I still haven’t gotten any yakuman at all in four-player mahjong; been tenpai for shousuushii once, but that happened on my second last draw and all the winning tiles were either discarded or in my opponents’ hands.

Anyway, my rate (for four-player) has been plummeting since the start of the month. I initially attributed it to plain bad luck but having placed badly for most of the last fifty games made me adjust my priors a bit. So yeah I just sort of suck at this game. At this rate (pun intended) I’ll probably get demoted from 2dan to shodan.

Some ~notes~ about that suuankou win for my personal reference. There are three tiles that complete the hand; namely, 1/6/9s. Winning by 1/9s with self-pick gives suuankou (8000 basic points; double basic points from every player). Winning by either of those tiles on a discard would lead to riichi (1 han) + toitoi (2 han) + san’ankou (2 han) + north (1 han), for 18000 points (3000 basic points; six times basic points from the player who dealt in). Possibly more with ura dora, but the ura dora indicator turned out to be 9p so whatever.

Toitoi is usually cheap (640 basic points without other yaku, though personally I try to ensure I have at least yakuhai or tan’yao first) but the dora can appear in multiples of three, making the hand expensive very quickly. Especially with kan or kan dora.

With a 9s the hand can be grouped up in two different ways. 777888999s can be interpreted as either 789s 789s 789s or 777s 888s 999s, where the former interpretation leads to riichi (1 han) + menzen tsumo (1 han) + iipeikou (1 han) + north (1 han) with 24 fu for “only” 1920 basic points, while the latter interpretation leads to an instant 8000 basic points.

With a 1s the only possible interpretation is as four triples (also 8000 basic points for tsumo, 3000 for ron), and with a 6s the only possible interpretation is as 777p 11s 678s 789s 789s, which is also 1920 basic points only (1280 if without menzen tsumo). Winning with 6s by discard would lead to 7700 points, or 7800 by self-pick.

Going solely by the discards and my own hand, there were two 1s, four 6s and and one 9s live, so (assuming I didn’t get any new dora or luck-based yaku other than menzen tsumo) my expected hand value was 296800/21≈14100 points. Looking back, calling riichi turned out to be a good idea, though I was playing under speed rules (3 seconds per turn + 5 extra seconds per round) so I didn’t really manage to think it out.

The first round of that particular game was won by me with a riichi chiitoi, and the second was an open toitoi san’ankou, then the third was the suuankou, and the left player got busted by the right player on the fourth round with an open hon’itsu after his fourth(!) discard. Incidentally, toitoi and chiitoi hands (and also hands with a shanpon wait) can be almost impossible to read because the tiles don’t need to have any relation with each other; setting up traps for players assuming you have a two-sided wait is particularly easy with these. (That said, chiitoi/toitoi inherently have bad waits; having better waits is likely more useful than making traps.)

Trivia (part 2)

3|111 and 1|113;
4|112 and 2|114;
6|114 and 4|116;
9|117 and 7|119.

This was a thing I noticed some time ago when I was bored couldn’t sleep and started mentally factoring integers. For obvious reasons anything ending in 3 or 7 is not divisible by 5, and at most one of 6\mid(10n+8) and 6\mid(10n+4) can be true; hence, of the seven possible statements of this form (d\mid(10n+d+2) and (d+2)\mid(10n+d) where d\in[1,7]\cap\mathbb Z) at most four can be true. This is attained exactly when n\equiv11\pmod{126}.

T, part 2

Re: T.

So the thing is over, and guess what, I ended up 22nd place. Despite only participating for a single day.

This probably would’ve been better blogging material if I somehow managed to be top ten, but alas.

There were over 400 participants who cleared at least ten races… but half of them didn’t even manage to clear twenty. Put it this way: anyone who didn’t even clear a hundred races obviously didn’t really care about the prize that’d require actual effort. How many people managed that? Only 61. (The person ranked directly above me didn’t clear a hundred races, but he’s also Sean Wrona. No other person in the top 48 cleared fewer than a hundred races.)

I have no idea how large TypeRacer’s player base is, but this kind of seems to indicate that this promotional event was a bit of a disaster.

On P versus NP

Disclaimer: things may be wrong, etc., but considering that this is another of those posts where I talk about how other people are wrong I’ll be trying a bit harder to be accurate.

P and NP are complexity classes of decision problems; i.e. problems with a Boolean answer. It is not, for example, meaningful to claim that factoring is in P or NP or PSPACE or EXPTIME because the output of factoring isn’t Boolean.

NP contains P. This confusion stems from a common depiction of P as “polynomial-time” and NP as “not-polynomial-time” when the N in NP really stands for “nondeterministic”. But the reality is more nuanced than that.

For some reason, discussion of co-NP is often omitted in pop science media, despite the fact that NP is asymmetric with respect to true/false outcomes. What a problem being in NP means is that there exists a polynomially-sized and polynomial-time-verifiable proof that the answer is “true” if it is “true”, but it doesn’t require any such proof for a “false” outcome. co-NP is the complement—a proof must exist for a “false” outcome, without any requirement of a proof if the answer is “true”. The result of omitting co-NP in plebeian discussion is that people end up talking about NP-intersect-co-NP instead of NP or co-NP when that’s what they really mean.

Here are two different formulations of the travelling salesman problem. A: Is the shortest route of length at most x? B: Is the shortest route of length at least x? A is in NP, B is in co-NP. Yet the optimisation version of the TSP (to find the shortest route) is sometimes called NP-complete, when it’s not even a decision problem and hence cannot be in NP. Oops!

As another example, it’s clear that primality testing (outcome is true if the input is a prime, false otherwise) is in co-NP. To prove compositeness, simply provide a nontrivial factor! Verifying the proof takes no longer than O(n^2) if long division is used, which is polynomial time. Prior to AKS, it was also known that primality testing was in NP, due to the ECPP algorithm. Of course, now that AKS exists (where “now” means “since 2002″), we know that PRIMES∈P so this example is somewhat moot.

There’s a bit of a mental block when it comes to thinking about whether the proof is provided by an adversary, but in the discussion of NP/co-NP, the assumption that the proof is correct is made. This can be resolved with an alternative definition. Instead of requiring a proof for a “true” answer, we can allow randomisation and say that there exists a polynomial-time algorithm such that if the answer is “true” it would output a “true” value with nonzero probability, but if the answer is “false” it must output “false”. The use of the “nondeterministic” adjective is most obvious in this interpretation—if the algorithm guesses the correct random numbers to use every time then it provides a polynomial-sized proof for every “true” answer, where the proof is the list of “random” numbers used. (This happens with vanishingly low probability, possibly on the order of 2^{-n} for an n-bit input.)

It also highlights the similarity to RP (randomised polynomial-time), which is the same, except that a “true” value must be output with a nonzero probability independent of the input for a “true” answer. Likewise, co-NP and co-RP can be defined similarly. P problems are automatically in RP, and RP problems are automatically in NP, so we have P⊆RP⊆NP and also P⊆co-RP⊆co-NP. It is believed that derandomisation is possible and therefore that P=RP=co-RP, but like every other open complexity theory question a proof in either direction is unlikely to surface for a pretty long time.

The next thing people misunderstand a lot is what it means for a problem to be NP-hard. For a problem to be NP-hard, it must be at least as hard to solve as every problem in NP. We could similarly define co-NP-hard, but since NP and co-NP are complements the classes end up being identical. As an NP-hard problem is not necessarily a decision problem, it consequently is not necessarily in either NP or co-NP. Those which are in NP are called NP-complete, and those which are in co-NP are called co-NP-complete. It is somewhat unfortunate that the term “NP-hard” leads people to infer that a problem is in NP, and I certainly have made that mistake before somewhere.