[SecretofMana]

You did a great job summarizing those topics concisely, but I have some quibbles about the P and NP stuff:

1. NP isn't the set of problems that can't be solved in a polynomial amount of time, but rather the set of problems that can be solved non-deterministically in polynomial time. This distinction is important, since this means by definition that P is a subset of NP, and furthermore means that uncomputable problems such as the Halting Problem do not belong in NP.

2. Your definitions for NP-completeness seem mixed up -- the polytime reduction property you're mentioning is the definition of an NP-hard problem, and you've said it backwards. If a problem is NP-hard, every problem in NP can be reduced to it in polynomial time (i.e. it is just as "hard" as every problem in NP). NP-completeness requires in addition to this the property that the problem itself is in NP. For example, although the Halting Problem is NP-hard, it is not NP-complete, since it is not in NP. NP-hardness of a problem can be shown by polytime reducing any NP-complete problem to it, since any problem in NP can be polytime reduced to the NP-complete problem.

[charlesju]

Sure, you're probably right. :)