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.
ReplyDeleteCan someone solve this communication complexity puzzle: Bob knows which two of 16 soccer teams played a game. His friend Alice knows who out of those 16 teams won the game (she doesn't know who the losing team was). What is the minimal amount of bits of information (0s and 1s) that must be communicated between Alice and Bob in order for Bob to find out who won?
ReplyDelete