This Schedule is Subject to Change.  The readings listed do not always contain everything presented in the lecture.


Jan 8 - Introduction

Jan 10 - Halting Problem.  (Read the subsection titled "An Undecidable Language" near the end of 4.2 of Sipser; or 7.2.2 of Moore&Mertens)
        - Turing Machines.  (Read 3.1 of Sipser (and 1.1 for a review of Finite Automata); or 7.5.1 of Moore&Mertens)
	

Jan 15 -  Church's Thesis.  3.3 of Sipser or 7.1.2 of MM
	    - recognizable  Page 142 of Sipser.  Pages 232 - 235 of MM
	

Jan 17 - recognizable and decidable
	    - complements of languages.  A is decidable iff complement(A) is decidable. 
 	    - If A and complement(A) are both recognizable then A is recognizable.
	    - universal Turing Machine; page 202 of Sipser, Section 7.5.1 of MM
	   

Jan 22 - enumerators Sec 3.2 of Sipser, Section 7.2.3 of MM


Jan 24 - Reducibility.  Section 5.1 of Sipser.  Pages 234-235 of MM
	    - Showing recognizability using dovetailing. 

Jan 29 -  T is not recognizable using diagonalization. 

Jan 31 -  The Post Correspondence Problem. Section 5.2 of Sipser; Section 7.6.3 of MM
		 - Hilbert'ss 10th problem (3.3 of Sipser; p. 228 of MM)
		 - complement(T) is not recognizable. 

Feb 5 -  Godel's Incompleteness Theorem (6.2 of Sipser; 7.2.5 of MM)

Feb 7 - Introduction to P (Chap 7 of Sipser, Chap 4 of MM)


Feb 12 - Informal definition of NP  (7.3 of Sipser, 4.1 of MM)

Feb 14 - formal definition of NP
            - verification algorithms (7.3 of Sipser, 4.3.1 of MM)
            - nondeterministic Turing Machines (3.2, 7.1 of Sipser)

Feb 26 - co-NP, polynomial time reducibility 

Feb 28 - more polytime reducibility
       - Cook-Levin Theorem  (7.4 of Sipser,  3.8, 5.1, 5.2 of MM)
       -  NP-complete (Def 7.34 of Sipser, Sec 5.1 of MM)

Mar 5 - SUBSET-SUM  (pg. 319-322 of Sipser, Sec 5.35 of MM)

Mar 7 - PRIME is in NP

Mar 12 - Factoring and cryptography

Mar 14 - Proof of the Cook-Levin Theorem

Mar 19 - PSPACE  Chap 8 of Sipser, Chap 8 of MM.

Mar 21 - NP is in PSPACE is in EXPTIME.  Logspace

Mar 26 - log space reducibility,  definition of NL-complete

Mar 28 - PATH is in co-NL

Apr 2  - PATH is NL-complete

Apr 4  - Savitch's Theorem, Undirected PATH is in L, wrapup