CS:5340 Limits of Computation
Fall 2017
12:301:45 TTh 61 SH (Schaeffer Hall)
Instructor:
Sriram V. Pemmaraju
Office: 101G MLH, srirampemmaraju@uiowa.edu, 3193532956
Office Hours: 1:302:30 M, 10:3011:30 W, 2:003: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, NPcomplete 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

Week 1: 8/218/25
Topics:
 Turing Machines (TMs) as a model of computation, definition of a ktape TM, A TM example
 The ChurchTuring Thesis
 Definition of a TM computing functions, accepting or deciding languages.
 Robustness of the TM definition

Week 2: 8/289/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/49/8
Topics:
 Time Efficiency of TMs, The complexity class DTIME(T(n)), The complexity class P,
Strong version of the ChurchTuring 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 Nondeterministic TMs (NDTMs), Equivalence of the two definitions of NP
Readings: Sections 2.1 and 2.2.

Week 4: 9/119/15
Topics:
 Polynomialtime reductions, NPhardness, NPcompleteness
 Example of a contrived NPcomplete language, TMSAT
 Preparation for the CookLevin Theorem
Readings: Section 2.3.

Week 5: 9/189/22
Topics:
 Proof of the CookLevin Theorem
 The classes coNP, coNPhardness, coNPcompleteness, Example
of a coNPcomplete problem: TAUTOLOGY
 The class NEXP, Proof of: P=NP implies EXP=NEXP
 Introduction to the deterministic Time Hierarchy Theorem

Week 6: 9/259/29
Topics:
Readings: Sections 3.1 and 3.3 and the proof of the Nondeterministic
Time Hierarchy Theorem from the lecture notes posted above.

Week 7: 10/210/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/910/13
Topics:
DSPACE, NSPACE, PSPACE, NPSPACE, L, NL and relationships among these classes
 PSPACEcompleteness, An example of a PSPACEcomplete problem: Generalized Geography
 PSPACEcompleteness of TQBF
Readings: Section 4.2

Week 9: 10/1610/20
Topics:
 PSPACEcompleteness of TQBF
 Savitch's Theorem, PSPACE = NPSPACE
 Implicitly logspace computable functions, logspace reductions, NLcompleteness
Readings: Section 4.2

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

Week 11: 10/3011/3
Topics:
 Example of EXACTINDSET, 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/611/10
Topics:
 Oracle Turing Machines
 Alternate definition the polynomial hierarchy using oracle TMs.
Readings: Section 5.5

Week 13: 11/1311/17
Topics:
 Introduction to circuit complexity, circuit families, and the class
P/poly.
 Undecidable languages in P/poly and showing that uniformP/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/2712/1
Topics:
 KarpLipton 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/412/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