Simple Guide To Complexity Theory
After reading Jeff’s terribly misguided post about NPcompleteness I thought to myself: “If Jeff, who seems to be completely clueless about complexity theory, can write a blog post about it then so can I.”
So without further ado, here’s ob’s complex guide to simplifying complexity theory.
First of all let’s get the definitions out of the way.
 Turing machine

An idealized computer, with infinite memory, an infinitely fast cpu, and unlimited bandwidth. It’s a mathematical model of computer so it can kick your Core 2 Duo’s sorry little ass faster than you can say Pentium.
Note

I originally wanted to make the point that bandwidth and cpu speed are irrelevant, but it seems to have confused more than clarified.) 
 Problem

In complexity theory, a problem is really a decision problem. It has a simple yes/no answer. You don’t ask “take this list and sort it and print the last ten items” that’s not a decision problem. You do ask “does this program, given this input, produce the last ten items of the sorted input?”.
Note

Although the sort problem as outlined here would be a valid decision problem, it is confusing since just changing my “last ten items” to “last C items” where C is a function of n would make it not be a decision problem. Better to use some other example, like “ is the number given prime?”) 
n

Size of the input for the turing machine. E.g. if your turing machine is sorting strings, like in the example above,
n
is the number of symbols that it takes as input. T(n)

Number of steps (i.e. instructions) that a turing machine must execute to solve a problem with input of size
n
. Polynomial Time

When
T(n)
can be expressed as an equation ofn
, and possibly some constants, using only addition, subtraction, multiplication, and constant nonnegative whole number exponents. E.g. n² is a polynomial while 2ⁿ is not.  Nondeterministic turing machine

A turing machine that can, at every branch point, take all possible branches in parallel. We call this guessing the optimal answer because, since the turing machine takes all branches, it must take the optimal branch too. If any of the parallel turing machines finds an answer, the nondeterministic turing machine stops and gives that answer (this means that it’s ok for some branches to never end).
So take your already idealized computer from above and make it able to reproduce itself on every branch point. I.e. it can follow all possible decisions in parallel.
P

The class of problems that can be solved by a turing machine in polynomial time.
NP

The class of problems that can be solved by a nondeterministic turing machine in polynomial time.
 Reducing a problem to another

Imagine you have two problems,
P1
andP2
. You know something aboutP1
(e.g. that it belongs toNP
). Now you want to prove some property ofP2
, for instance, that it belongs toNP
as well.
One technique is to show that if we could solve P2
in polynomial
time (i.e. P2
belongs to P
), we could use that answer to solve
P1
in polynomial time. This would mean that P1
belongs to P
which is a contradiction. This technique is called reductio ad
absurdum.
Note

I completely botched this and commenter Bibi correctly called me on it. Here’s an attempt to clarify a reduction: if you want to solve an instance of P2, you convert it to an instance of P1, and then solve P1 to get an answer. Thus, you’ve reduced P2 to P1. How’s that?) 
 NPcomplete

We say a problem is NPcomplete if it satisfies two properties: 1) it belongs to
NP
, and 2) every other problem that belogs toNP
can be reduced, in polynomial time, to it.
This means that if we come up with a solution for an NPcomplete
problem that runs in polynomial time in a deterministic turing machine
(i.e. belongs to P
), any other problem in NP
can be solved in
polynomial time by first reducing it (again, in polynomial time) to
this problem, and using our solution. We would have proved that P =
NP
and we would have also won (pinky to corner of mouth)
one million dollars.
 NPhard

A problem
P1
, that is so hard, that even though we can prove number two above, we can’t prove number one. This means we knowP1
to be just as hard as anything inNP
and possibly harder, but we don’t know ifP1
is inNP
or not.P1
is very likely to require exponential time.
Note

I stand by my definition of NPhard. Although not being able to prove #1 is a sufficient condition, it is not necessary. All problems in P are in NP, and yet we call them P, not NP. Thus, even if all problems that are NPcomplete are also NPhard, it’s uninteresting to call an NPcomplete problem NPhard. The point of calling a problem NPhard is that, it’s really hard! Even if it turned out that P = NP, an NPhard problem might still be hard!) 
So there you have it, go impress your friends. I hear that “hey, baby! your love is NPhard to get” is a very successful pickup line at pubs around M.I.T.