You better watch out, you better not (ﾉゝ∀･)〜綺羅星☆, otherwise Santakuto will rip a hole in space-time and punch your robot mask off. Instead, let’s take some time over the next two weeks and come back to this annual tradition to think back to the good times that anime has given us over the past year. And so the adventure of life goes on.
Naohito Takayama is an ordinary high school boy who dreams of a comfortable future working for the top-rated Toronto Transit Commission. He is assigned as a trainee in the Subway Security Force full of odd characters such as Sakurai, a troublemaker who hates men. On top of that, an extremist group called “PC” plots to privatize the Toronto Transit Commission.
It’s Takayama and friends’ first day on the job. They help an old lady who is confused by the maps on the TR because stations that are lit green are the ones the train has actually already been to, not the ones that the train is headed towards. A thief attempts to make his escape on a train at Donlands station but gets caught because no one ever got told that trains were out of service and replaced with shuttle buses.
Takayama and friends receive a bomb threat at Bessarion station. They attempt to look for the bomb. They evacuate the three people who usually wait for trains at Bessarion. They find it and are able to perform a controlled explosion in the nearby empty field, where promises of condos and intensified development never came to fruition.
Takayama runs into one of his old friends who has really sensitive hearing. They are on a TR and it hurts her ears when the door-closing chimes play because the TR doesn’t have speakers on the exterior of the trains so they have to play the chimes really loud for anyone on the platform to hear.
I had originally not planned on writing anything because lmao blogging and also because I was content to keep my being きもい on twitter. However, I’d learned that not only was it Oreki’s birthday today, but it’s also the release date for the PC version of Clannad, making this some sort of anime holy day for me. Even spookier is that this year marks Clannad’s 10th anniversary, a fact that I only know because I found and bought the 10th anniversary artbook while I was in Tokyo this past summer.
It might seem really trite nowadays (some might argue that it already was when it aired), but Clannad continues to hold a special place in my heart and is still one of my favourite anime and visual novels. Even back then knowing almost nothing about visual novels, it was really easy to see all of the different pieces glued together into a single coherent story.
Where I think Clannad flops is if you think of Clannad as the story of Tomoya and Nagisa getting together in high school. It’s nice, but it’s pretty typical. What I consider Clannad to be and what interested me the most about it is Tomoya’s story beyond his high school life and romance and where he ends up as a person. But maybe this speaks more about my endearment for moe guy characters than how good Clannad is.
I think that’s also why I like Oreki so much (I mean other than being moe). Hyouka is even less about Oreki’s love life and much more about how he changes between episodes 1 and 22. Of course, a lot of that has to do with Chitanda (a lot like how Tomoya changes because of Nagisa). Of course, Oreki’s not done by the time episode 22 rolls around and the way the show ends makes that pretty clear.
Now back to waiting for a new KyoAni show starring moe boy voiced by Nakamura Yuuichi.
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).
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.