http://www.csc.villanova.edu/~japaridz/SDU2013/

 

Computability and Complexity

2013-08-05  2013-08-16

 

Instructor: Giorgi Japaridze

 

Office Hours: By appointment

 

Grading: There will be an examination on August 21, 9:00-11:00 AM. No books, notes, computers, cellular phones etc. will be allowed during it.

 

Textbook: "Introduction to the Theory of Computation" by Michael Sipser. Cengage Learning, 2013. ISBN 978-1-133-18779-0 (3rd edition; the earlier editions are also fine, except that there can be some discrepancies in the numbering of theorems, definitions and exercises). Having this textbook is not necessary, but may be helpful.

 

Lecture Notes:

 

The Church-Turing Thesis (Chapter 3)  

Decidability (Chapter 4)   

Reducibility (Chapter 5)   

Measuring Complexity (Section 7.1)  

The Class P (Section 7.2)   

The Class NP (Section 7.3)   

NP-Completeness (Section 7.4)   

Additional NP-Complete Problems (Section 7.5)   

Space Complexity (Section 8.0)  

Savitch's Theorem (Section 8.1)  

The Class PSPACE (Section 8.2)   

PSPACE-Completeness (Section 8.3)   

The Classes L and NL (Section 8.4)   

NL-Completeness (Section 8.5)    

NL Equals coNL (Section 8.6)   

Hierarchy Theorems (Section 9.1)   

Relativization (Section 9.2)   

Circuit Complexity (Section 9.3)   

Approximation Algorithms (Section 10.1)   

Probabilistic Algorithms (Section 10.2)   

Alternation (Section 10.3)   

Interactive Proof Systems (Section 10.4)   

Parallel Computation (Section 10.5)   

 

 

Covered material and sample questions that could be asked on the examination:

 (60%-90% of the examination questions will come from this list)

 

[August 5] Slides 3.0.a – 3.2.a.

[August 6] Slides 3.2.e – 5.1.a.

[August 7] Slides 5.3.a – 7.2.f (7.2.g has been omitted and will not be asked).

 [August 8] Slides 7.3.a – 7.4.i 

 [August 9] Slides 7.4.j, 7.5.a – 7.5.o (Slides 7.4.k – 7.4.v and 7.5.p – 7.5.s omitted)

[August 12] Slides 8.0.a – 8.3.b

[August 13] Slides 8.3.c – 8.5.d (proof idea for Theorem 8.9 on slide 8.3.c omitted)

[August 14] Slides 8.5.e – 8.6.d  

[August 15] Slides 9.1.a – 9.1.e  (Slide 9.1.f, and all subsequent materials, will be omitted)

[August 16] Review


Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: visit tracker on tumblr