Computational Complexity

Friday, May 01, 2009

 
Foundations of Complexity

Posted by Lance

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. 

1. What is a Computer?
2. Computable and Computably Enumerable Languages
3. Universal Turing Machines and Diagonalization
4. Noncomputable Computably Enumerable Languages
5. Reductions
6. The Halting Problem
7. The Recursion Theorem
8. Efficient Computation
9. Nondeterminism
10. The P versus NP Problem
11. NP-Completeness
12. Turing Machine Redux
13. Satisfiability
14. CNF-SAT is NP-complete
15. More NP-complete Problems
16. Ladner's Theorem 
17. Space Complexity
18. Savitch's Theorem
19. The Immerman-Szelepcsényi Theorem

I hope to add more lessons in the future.

7:40 AM # 5 comments

1.  Alex McFerron says:  
   
   This is great. thanks!
   

   11:30 AM, May 01, 2009

2.  Anonymous says:  
   
   Does anyone know anything about the supposed ~60 postdocs that are to be announced via NSF stimulus funds? Is there an announcement yet?
   

   10:07 PM, May 01, 2009

3.  Anonymous says:  
   
   Does anyone know anything about the supposed ~60 postdocs that are to be announced via NSF stimulus funds? Is there an announcement yet?
   If 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 ?
   

   3:35 PM, May 03, 2009

4.  Anonymous says:  
   
   The links are broken. Could they be fixed? They look like valuable material. Thanks
   

   9:38 PM, June 20, 2010

5.  Lance says:  
   
   The links should have forwarded properly but I updated them just in case.
   

   9:21 AM, June 21, 2010

Comment Feeds: This Post All