The fourth annual π/ホワイト day animaths appreciation post

Qualia 8

Let us celebrate this day with Nadeko.

Okay, now let’s figure out what the hell Alice is trying to claim. Alice can solve equations by turning them into pictures and solve them instinctively like that. What implications does this have?

First, we probably want to talk about what the P/NP problem is. In computational complexity, we talk about the complexity of problems and we measure this as the amount of resources we need to solve a problem. The two most common measures are for time and space. That is, roughly the amount of time it takes to solve a problem or the amount of space (so, like memory) that’s required to solve a problem. This is expressed as a function of the size of the input.

Formally, all of this stuff is defined in terms of Turing machines, but we don’t need that level of specificity. Intuitively, we can think of P as the class of problems which we can solve in a reasonable amount of time (or “efficiently”) and NP as the class of problems for which we can verify the correctness of a given solution in a reasonable amount of time. By reasonable, we mean that the amount of time it takes scales reasonably depending on the size of the input or problem we want to solve.

The P/NP problem asks whether P is equal to NP. If you think about it for a bit, it seems kind of intuitive that those two classes shouldn’t be equal. It’s a lot easier to figure out whether an answer to a problem is correct than it is to find a correct answer. And most computer scientists also agree that that’s probably the case. The hard part is actually proving it, which no one has been able to do since 1971, when U of T’s Stephen Cook first formulated the problem.

The classical NP-complete problem is the satisfiability problem. If I have a boolean formula, is there an assignment of true/false values that makes the formula evaluate to true? Testing this is easy: if you give me an assignment that you claim works, I can check it in the amount of time it takes to look at each variable. Trying to come up with an assignment is a lot trickier. The easiest thing to do is try trial and error, but that could take an exponential amount of time. Of course, there are a lot of fancy tricks we’ve come up with for this problem, but we still have no way of solving this problem in a way that we can say is theoretically efficient (whether it’s the case for practical uses is a different matter).

What’s baffling about P/NP is that the idea is rather simple to prove or disprove. We have these notions of hardness and completeness which allow us to reduce problems to other problems. In particular, the class of NP-complete problems are those problems which are called NP-hard and contained in the class NP. These problems have the property of being able to reduce to any other NP-complete problem.

A reduction basically says that two problems are about as computationally hard as each other. The idea is that if I have some problem I want to solve but I don’t know how to do it, I can transform it (with a reasonable amount of time) into some other problem that I hypothetically do know how to solve. The reasoning is that if I can do that, then I know that the problem I wanted to solve takes about as much resources to solve as the problem I already know how to solve. And it’s pretty remarkable, then, that every NP-complete problem has this property of being able to reduce to any other one.

So the way to prove that P=NP is to figure out a way to solve any NP-complete problem in polynomial time. Since every NP-complete problem reduces to every other one, you just have to choose your favourite (read: easiest) NP-complete problem out of the several thousand that we know of and figure out an efficient algorithm for it. Because of the reducibility property, if you solve one efficiently, you’ve basically solved them all efficiently. This means that all problems in NP can be solved efficiently and it turns out P=NP. And yet, no one has been able to come up with an efficient algorithm for any NP-complete problems.

On the other hand, while at this point it’s pretty obvious that P≠NP, we have no idea how to prove it. The field of computational complexity and all the tools that we’ve developed over the last few decades are all interesting and useful, but they were all in an attempt to show that P≠NP and so far, nothing we’ve thrown at it has stuck. In fact, we’ve ended up creating a lot more questions that seem to have interesting structures and intuitive answers but we still have no way of proving a lot of these conjectures.

Of course, in the last decade or two, there’s been a lot of focus on quantum computing and with the rise of quantum computing, quantum complexity theory. It’s commonly believed that quantum computing gives us exponential speedup and allows us to solve NP-complete problems in polynomial time.

Well, it doesn’t.

The idea is that since you have a bunch of states in superposition, you also have all possible outcomes stored in those states. Unfortunately, it doesn’t work like that and there are a bunch of complications that arise in trying to extract outcomes of computations stored in qubits that render this whole point moot.

There’s nothing inherent in quantum computing that brings us closer to actually resolving questions that we have about the complexity hierarchy we’ve defined. In fact, quantum computations can be simulated on classical computers in exponential time, so it’s not like there’s nothing we don’t already know about computation, we can just certain kinds of computations faster.

And just like the other tools we’ve developed in computational complexity to try and resolve this question, quantum computing throws another wrench into the problem by introducing quantum analogues of classical complexity classes. Some of these, like QIP, the class of problems solvable by quantum interactive protocols, turn out to have no additional power (it was proved in 2010 by Jain, Ji, Upadhyay, and Watrous that QIP = IP). And some, like BQP, the class of problems solvable in bounded-error polynomial time, have the same problem where we’re not entirely sure how it relates to the other classes.

So knowing all of this, what does Alice’s claim mean exactly? Unsurprisingly, it doesn’t mean anything. If Alice can solve equations intuitively by drawing pictures, then she can probably already solve PSPACE-complete problems (since there are equation problems which are known to be in PSPACE), which means that it doesn’t even matter whether or not she has access to a quantum computer, since she can already solve problems harder than the ones in the quantum analogues of P and NP.

The lesson here is that little girls would not necessarily make very good mathematicians even if they can compute computationally intractable problems (this is basically what Gödel’s incompleteness theorems say too).

Maoyuu: Points of order

Here, we can see the demons do not subscribe to the 'living tree' doctrine of constitutional interpretation.

Here, we can see the demons do not subscribe to the ‘living tree’ doctrine of constitutional interpretation.

In the latest chapter of Maoyuu, the Demon Queen faces a confidence vote through a little-known clause of the demons’ constitution. Of course, there appear to be some glaring issues with the demons’ constitution and the procedural bylaws governing the council made up of the eight leaders of the largest clans. This allows our heroes to save the Demon Queen through the classic practice of abusing procedure.

The Blue Demon King, King of the Blue Demons, moves to remove the Demon Queen from office. We can think of this as a confidence motion and it requires a simple majority for it to pass. There are some interesting details here. For instance, the threshold for passing is 50%, not 50% + 1. Also, the Demon Queen appears to have no voting rights in this case, so she’s at the mercy of the members of council. In this case, there are eight members with voting rights, which means that the Demon Queen can be removed with just four votes.

Interestingly enough, they don’t really debate the motion and just kind of wander off to strategize on their own for a few hours before returning to vote. For some reason, they speak when they vote, which really is not a good idea. You don’t really want any shenanigans to be going on while members vote.

Since there are only eight members, the vote becomes 4-2-1 in favour of removing the Demon Queen by the time it’s the Fire Dragon Archduke’s turn to speak and vote, which means it’s a victory for the opposition. The opposition begins to get up and shut the whole thing down since it’s pretty clear they’ve won, but the Fire Dragon Archduke doesn’t have any of it and insists on his right to speak and vote, a classic legislator move.

The other members relent and allow the Fire Dragon Archduke to speak and he uses the chance to play for time. A councillor once mentioned that if they didn’t know what was going on and it wasn’t clear that they’d win that vote, what you’d do is hit the button to put your name on the list up to speak and buy time. Incidentally, this is one of the reasons why in most legislatures around the world, speaking occurs before voting.

Another common feature of most legislatures is that you can’t interrupt a vote once it’s started. Here, we see why this is the case. The Fire Dragon Archduke was buying time for a human delegation to arrive at council. When they do, the Fire Dragon Archduke moves to allow the humans to form a new clan and claim representation on the council, invoking another little-known clause in the demons’ constitution. This is seconded by the Ogre Princess Shrine Maiden and the humans are allowed to sit on the council with full rights since, according to the constitution, the creation and addition of a clan doesn’t require a vote. Of course, with them added, the vote becomes 4-4-1 and the confidence motion loses.

The lesson here is that constitutions are important and procedure is important.

12 Days XI.5



Sometime during the broadcast of Tamako Market or Chu2koi, I mentioned that Kyoani should really consider doing a show like K-ON! but with boys because they are able to make their boys as moe as their girls. Twitter user Yuyucow alerted me to the website of Animation Do which had a visual for an unnamed project involving boys and swimming. A few months later, a CM involving boys and swimming aired after the end of a Tamako Market episode and the rest is history.

12 Days XI: Sad Oreki in school



Iris Zero is Hyouka except the Oreki Houtarou here has been bullied since childhood and loves cakes. He gets by keeping as low a profile as possible, until he’s dragged out of his shell by a familiarly meddlesome cute girl. This was what I turned to when Hyouka finished airing last year. Unfortunately, I wasn’t prepared for the mangaka to fall ill and go on hiatus for a year and a half. Thank goodness it’s back as of this October so it can continue to feed me while I wait in vain for KyoAni to animate more Hyouka.

12 Days X: Unfinished cut



On the other hand, the existence of a Kizumonogatari anime remains a mystery. Of course, given the track record of many light novel anime, I don’t think I would’ve expected back in 2009 that I’d still be watching Monogatari in 2013. Bakemonogatari seemed pretty conclusive, which made Nisemonogatari feel kind of superfluous for me. What’s surprising about Monogatari Second Season is that it shows us that, no, that first batch of stories wasn’t really all. But now we know that this still isn’t over and Nisio Isin can still produce words about Koyomi Ararararagi et. al, so we may be wondering where the hell he’s going with this for a while.