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.