Computational Complexity
goodmath | September 6, 2007 Suppose you've got a huge graph - millions of nodes. And you know that it's not connected - so the graph actually consists of some number of pieces (called the connected components of the graph). And there are constantly new vertices and edges being added to the graph, but nothing is ever removed. Some questions you might want to ask about this graph at a particular point in time are:
How many components are there in the graph?
Which component is vertex X in?
Are vertices X and Y in the same component?
How many components are there?
All of these questions are variants of a classic…
goodmath | September 3, 2007 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…
goodmath | April 7, 2007 For the basics, I wrote a bunch of stuff about sorting. It seems worth taking a moment
to talk about something related: binary search. Binary search is one of the most important
and fundamental algorithms, and it shows up in sorts of places.
It also has the amazing property that despite being simple and ubiquitous, it's virtually
always written wrong. There's a bit of subtlety in implementing it correctly, and virtually
everyone manages to put off-by-one indexing errors into their implementations. (Including me; last time I implemented a binary search, the first version included one of the…
goodmath | February 28, 2007 Multiple people have written to me, after seeing yesterday's
href="http://scienceblogs.com/goodmath/2007/02/basics_algorithm_1.php">algorithms basics post, asking me to say more about sorting algorithms. I have to say that it's not my favorite topic - sorting is one of those old bugaboos that you can't avoid, but which gets really dull after a while. But there is a kernel of interest to it - sorting can be used to demonstrate a lot of interesting ideas about
computational complexity.
In that vein, let's start with a little bit of complexity. There's actually a trick based on Kolmogorov/…
goodmath | January 16, 2007 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…
goodmath | January 9, 2007 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…
goodmath | January 8, 2007 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.
So, what are P and NP?
P and NP are two very broad classes of computational problems. When we're talking about P and NP, we're talking about the intrinsic complexity of a problem - that is, a minimum complexity bound on the growth rate of the worst case performance of any algorithm that solves the problem.
P…