In the first year of this blog I wrote a series of "lessons" to give an informal introduction to computational complexity but I never wrote a single post that links to them all.
- What is a Computer?
- Computable and Computably Enumerable Languages
- Universal Turing Machines and Diagonalization
- Noncomputable Computably Enumerable Languages
- Reductions
- The Halting Problem
- The Recursion Theorem
- Efficient Computation
- Nondeterminism
- The P versus NP Problem
- NP-Completeness
- Turing Machine Redux
- Satisfiability
- CNF-SAT is NP-complete
- More NP-complete Problems
- Ladner's Theorem
- Space Complexity
- Savitch's Theorem
- The Immerman-Szelepcsényi Theorem
This is great. thanks!
ReplyDeleteDoes anyone know anything about the supposed ~60 postdocs that are to be announced via NSF stimulus funds? Is there an announcement yet?
ReplyDeleteDoes anyone know anything about the supposed ~60 postdocs that are to be announced via NSF stimulus funds? Is there an announcement yet?
ReplyDeleteIf you are referring to the 30 new stimulus funded NSF Math Institute postdoc positions -- these positions have already been been filled. I don't know where you got the number 60 from ?
The links are broken. Could they be fixed? They look like valuable material. Thanks
ReplyDeleteThe links should have forwarded properly but I updated them just in case.
ReplyDelete