**[course overview**
| **lectures**
| **assignments**
| **related material]**

**Instructor:** James R.
Lee,
CSE 640

Time: Tuesdays and Thursdays in THO 211, 10:30-11:50am.

**Office hours:** Tues 2:30-4pm, CSE 640

**Teaching assistant:** Yi-Shu Wei

**Office hours:** Mon 1:30-2:30pm, CSE 218

**Course evaluation: **Scribe one lecture, homeworks, and a final exam.

**About this course:**

This course is about computation, proofs, logic, and the nature of truth.
We will study what problems can (and cannot) be solved
by a computer, as well as how much of a given resource is needed to solve them
(time, memory, randomness). In doing so, we'll touch upon
some of the most important mathematical (and sometimes philosophical) discoveries of the 20 and 21st centuries, as well as confront (time and again) the
limits of our present understanding.

Lecture | Date | Topic | Reading | Scribe |

Lecture 1 | Tues, Apr 1 | Cantor, set theory, and diagonalization | Logicomix, Ch. 1-2 | notes |

Lecture 2 | Thurs, Apr 3 | Turing machines | Logicomix, Ch. 3; Sipser, 3.1-3.2 | notes |

Lecture 3 | Tues, Apr 8 | Algorithms on Turing machines | Sipser, 3.2-3.3 | notes |

Lecture 4 | Thurs, Apr 11 | The Church-Turing Thesis, decidability of simpler models | Sipser, Ch. 4 | notes |

Lecture 5 | Tues, Apr 15 | The Halting Problem, undecidable languages | Sipser, Ch. 4 | notes, |

Lecture 6 | Thurs, Apr 17 | Reductions, the Recursion Theorem | Sipser, Ch. 5, 6.1 | n1, n2 |

Lecture 7 | Tues, Apr 22 | Logic, proofs, and incompleteness | Sipser, Ch. 5, 6.2; [Supp] Papadimitriou, Ch. 5; [Supp] Logicomix, Ch. 4-6 | notes |

Lecture 8 | Thurs, Apr 24 | The first incompleteness theorem | Sipser 6.2; [Supp] Papadimitriou, Ch. 6; [Supp] Logicomix, Ch. 4-6 | notes |

Lecture 9 | Tues, Apr 29 | Time complexity | Sipser 7.1 | notes |

Lecture 10 | Thurs, May 1 | P and NP | Sipser 7.2-7.3 | notes |

Lecture 11 | Tues, May 6 | NP-completeness | Sipser 7.3-7.4 | notes |

Lecture 12 | Thurs, May 8 | The Cook-Levin Theorem | Sipser 7.4-7.5 | notes |

Lecture 13 | Tues, May 13 | NP-completeness reductions I | Sipser 7.5 | notes |

Lecture 14 | Thurs, May 15 | NP-completeness reductions II | Sipser 7.5 | notes |

Lecture 15 | Tues, May 20 | Space complexity and Savitch's Theorem | Sipser 8.1-8.2 | n1, n2 |

Lecture 16 | Thurs, May 22 | P vs. PSPACE vs. EXPTIME, and Hierarchy Theorems | Sipser 8.2, 9.1 | notes |

Lecture 17 | Thurs, May 27 | Space and Time Hierarchy Theorems | Sipser 9.1 | notes |

Lecture 18 | Thurs, May 29 | Logspace | Sipser 8.4 | notes |

Lecture 19 | Thurs, Jun 3 | Connectivity with random bits | ||

Lecture 20 | Thurs, Jun 5 | SL=L |

Secondary material [no need to purchase]: Logicomix and Computational Complexity by Christos Papadimitriou.

**For writing scribe notes:** If you are using LaTeX, please use this template. If you are using Microsoft Word, see these notes on Microsoft Equation Editor. Briefly, there is a very rich syntax for quickly typing mathematical text.

These can be turned in electronically (scan or typeset--no fuzzy smartphone photos) by sending them to cse431-staff@cs by class time on the due date.

- Homework #0, due Thursday, April 10th.
- Homework #1, due Thursday, April 17th.
- Homework #2, due Thursday, April 24th.
- Homework #3, due Thursday, May 1st.
- Homework #4, due Thursday, May 8th.
- Homework #5, due Thursday, May 15th.
- Homework #6, due Thursday, May 21st.
- Homework #7, due Tuesday, June 3rd.