CS:5340 Limits of Computation
Fall 2017

Instructor:
Sriram V. Pemmaraju
Office: 101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
Office Hours: 1:30-2:30 M, 10:30-11:30 W, 2:00-3:00 F (and by appointment)

Course website: http://www.cs.uiowa.edu/~sriram/5340/fall17/
Department website: http://www.cs.uiowa.edu/

Overview
This course is a mathematical exploration of the limits of the power of computers and computation. Some of the questions we ask and attempt to answer are the following: are there problems that cannot be solved on any computer? What are some examples of these unsolvable problems? How do we prove that a problem is computationally unsolvable? If we place bounds on the resources (time and space) available to a computer, then what can be said about which problems can and cannot be solved on a computer? How do we show that as the resources (time and space) that a computer uses, are increased then the collection of problems that can be solved grows? How does the power of a computer change, if it has access to random bits? How does getting a limited amount of "advice" increase the power of a computer? What if the computer could interact in a limited way with a powerful advisor?

In attempting to answer these questions we will study models of computation such as Turing machines and Boolean circuits, time complexity classes such as P, NP, NP-complete and those in the polynomial hierarchy, space complexity classes such as PSPACE, L and NL, and randomized complexity classes such as RP and BPP. We will also study interactive proofs and the corresponding complexity class IP and touch upon the surprising result that IP = PSPACE.

Syllabus document, Announcements, Homeworks and Exams, Weekly Topics, Online Resources

Homeworks and Exams

• Homework 1. Due in class on Thu, 8/31.
• Homework 2. Due in class on Tue, 9/12. Homework 2 Hints.
• Homework 3. Due in class on Thu, 9/21.
• Homework 4. Due in class on Tue, 10/3.
• Homework 5. Due in class on Thu, 10/26.
• Homework 6. Due in class on Tue, 11/28.
• Homework 7. Due by 5 pm, Fri, 12/8.

Announcements

• I will be out of town on Fri, 9/1 and will not be holding office hours that day.
• There is no class on Tue, Sep 12th and I will not have office hours on Wed, Sep 13th. Submit HW2 solutions to my mailbox by 5 pm on Tue, Sep 12th.
• Midterm is on Fri, Oct 6th 2017 in 203 Becker Communication Studies Building (BCSB) from 6:30 pm to 8:30 pm.
• Here are some details on the upcoming midterm exam.
• The final is on Tue, 12/12 in 205 MLH from 10:00 am to noon. Here are some details on the upcoming final exam.

Weekly Topics

• Week 1: 8/21-8/25
  Topics:
  • Turing Machines (TMs) as a model of computation, definition of a k-tape TM, A TM example
  • The Church-Turing Thesis
  • Definition of a TM computing functions, accepting or deciding languages.
  • Robustness of the TM definition

• Week 2: 8/28-9/1
  Topics:
  • Robustness of the TM definition: simulating one TM variant on another with polynomial slowdown.
  • Universal TMs, diagonalization argument for uncomputability of certain functions, uncomputability of HALT

• Week 3: 9/4-9/8
  Topics:
  • Time Efficiency of TMs, The complexity class DTIME(T(n)), The complexity class P, Strong version of the Church-Turing Thesis
  • Examples of problems/languages known to be in P and examples of problems/languages not known to be in P
  • Verifier definition of the class NP, examples of problems in NP, showing that problems are in NP
  • The class EXP, showing that P is contained in NP and NP is contained in EXP
  • Defining NP via Non-deterministic TMs (NDTMs), Equivalence of the two definitions of NP
  Readings: Sections 2.1 and 2.2.

• Week 4: 9/11-9/15
  Topics:
  • Polynomial-time reductions, NP-hardness, NP-completeness
  • Example of a contrived NP-complete language, TMSAT
  • Preparation for the Cook-Levin Theorem
  Readings: Section 2.3.

• Week 5: 9/18-9/22
  Topics:
  • Proof of the Cook-Levin Theorem
  • The classes coNP, coNP-hardness, coNP-completeness, Example of a coNP-complete problem: TAUTOLOGY
  • The class NEXP, Proof of: P=NP implies EXP=NEXP
  • Introduction to the deterministic Time Hierarchy Theorem

• Week 6: 9/25-9/29
  Topics:
  • Proof of the Deterministic Time Hierarchy Theorem
  • The Non-deterministic Time Hierarchy Theorem and its proof. We will discuss the proof in these lecture notes by Jonathan Katz of University of Maryland. This proof is relatively recent and it appears in this 2010 arxiv paper by Fortnow and Santhanam.
  Readings: Sections 3.1 and 3.3 and the proof of the Non-deterministic Time Hierarchy Theorem from the lecture notes posted above.

• Week 7: 10/2-10/6
  Topics:
  • Ladner's Theorem on the existence of "NP Intermediate" languages.
  • Introduction to space complexity classes.
  Readings: Section 3.3 and Section 4.1.

• Week 8: 10/9-10/13
  Topics:
  DSPACE, NSPACE, PSPACE, NPSPACE, L, NL and relationships among these classes
  • PSPACE-completeness, An example of a PSPACE-complete problem: Generalized Geography
  • PSPACE-completeness of TQBF
  Readings: Section 4.2

• Week 9: 10/16-10/20
  Topics:
  • PSPACE-completeness of TQBF
  • Savitch's Theorem, PSPACE = NPSPACE
  • Implicitly logspace computable functions, logspace reductions, NL-completeness
  Readings: Section 4.2

• Week 10: 10/23-10/27
  Topics:
  • Transitivity of logspace reductions and other properties
  • PATH is NL-complete
  • Certificate definition of NL
  • Introduction to the polynomial hierarchy
  Readings: Section 4.2, Section 5.1

• Week 11: 10/30-11/3
  Topics:
  • Example of EXACT-INDSET, which is not in NP, but is in Sigma_2.
  • Properties of the polynomial hierarchy (e.g., P = NP implies that the hierarchy collapses to level 1).
  • Complete problems for Sigma_i and Pi_i
  Readings: Sections 5.1 and 5.2

• Week 12: 11/6-11/10
  Topics:
  • Oracle Turing Machines
  • Alternate definition the polynomial hierarchy using oracle TMs.
  Readings: Section 5.5

• Week 13: 11/13-11/17
  Topics:
  • Introduction to circuit complexity, circuit families, and the class P/poly.
  • Undecidable languages in P/poly and showing that uniform-P/poly = P
  • Relationship between P and P/poly
  • Alternate definition of P/poly via TMs that take advice
  Readings: Sections 6.1, 6.2, and 6.3

• Week 14: 11/27-12/1
  Topics:
  • Karp-Lipton Theorem showing that is NP is a subset of P/poly then the polynomial hirarchy collapses to level 2.
  • Shannon's result showing that most functions need exponential size circuits.
  • Introduction to randomized computation, the class BPP, examples of randomized algorithms: randomized median finding
  Readings: Theorem 6.19 and its proof, Section 7.1

• Week 15: 12/4-12/8
  Topics:
  • The classes RP, coRP, and ZPP
  • Robustness of definitions of randomized complexity classes
  • BPP is a subset of P/poly
  • BPP is in the polynomial hierarchy
  Readings: Sections 7.3, 7.4, and 7.5