There are a lot of very cool problems in computer science that can be solved by using
an appropriate data structure; and the data structures are often easiest to describe in terms
of graphs. And of those data structures, one thing that often comes up is amortized algorithmic complexity. Amortized complexity is something which has been occupying my thoughts lately,
because it’s come up in several real problems, so I’m in the mood to write about it, and it’ll be
useful later.

The idea of amortized complexity is that for some structures, the worst case complexity
cost of a series of operations is different from the worst-case complexity of a single operation. In amortized complexity, you consider cases where some operation is inexpensive most of the time – but to keep it inexpensive most of the time, you need to periodically do something expensive.

Continue reading →

What started me on this whole complexity theory series was a question in
the comments about the difference between quantum computers and classical
computers. Taking the broadest possible view, in theory, a quantum computer
is a kind of non-deterministic machine – so in the best possible case,
a quantum machine can solve NP-complete problems in polynomial time. The set
of things computable on a quantum machine is not different from the set of
things computable on a classical machine – but the things that are tractable (solvable in a reasonable amount of time) on a quantum
computer may be different.

Continue reading →

As I’ve mentioned in the past, complexity theory isn’t really one of my favorite topics. As a professional computer scientist, knowing and loving complexity up to the level of NP-completeness
is practically a requirement. But once you start to get beyond P and NP, there are thousands of complexity classes that have been proposed for one reason or another, and really understanding all of them can get remarkably difficult, and what’s worse, can feel like an utterly pointless exercise,
particularly if the writer/teacher you’re learning from isn’t very good.

I’m not going to write a long series of posts on the more esoteric complexity classes. But there
are a few that are interesting, and might even have some relevance to actual practical problems in
selecting algorithms for a software system.

Continue reading →

Now that we’ve gone through a very basic introduction to computational complexity, we’re ready
to take a high-level glimpse at some of the more interesting things that arise from it. The one
that you’ll hear about most often is “P vs NP”, which is what I’m going to write about today.

Continue reading →