CS:5340 Limits of Computation
12:30-1:45 TTh 61 SH (Schaeffer Hall)
Sriram V. Pemmaraju
Office: 101G MLH, firstname.lastname@example.org, 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/
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.
Homeworks and Exams,
- 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.
Week 1: 8/21-8/25
- 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
- Robustness of the TM definition: simulating one TM variant on another with polynomial
- Universal TMs, diagonalization argument for uncomputability of certain
functions, uncomputability of HALT
Week 3: 9/4-9/8
Readings: Sections 2.1 and 2.2.
- 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
- 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
Week 4: 9/11-9/15
Readings: Section 2.3.
- Polynomial-time reductions, NP-hardness, NP-completeness
- Example of a contrived NP-complete language, TMSAT
- Preparation for the Cook-Levin Theorem
Week 5: 9/18-9/22
- 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
Readings: Sections 3.1 and 3.3 and the proof of the Non-deterministic
Time Hierarchy Theorem from the lecture notes posted above.
- 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.
Week 7: 10/2-10/6
Readings: Section 3.3 and Section 4.1.
- Ladner's Theorem on the existence of "NP Intermediate" languages.
- Introduction to space complexity classes.
Week 8: 10/9-10/13
DSPACE, NSPACE, PSPACE, NPSPACE, L, NL and relationships among these classes
Readings: Section 4.2
- PSPACE-completeness, An example of a PSPACE-complete problem: Generalized Geography
- PSPACE-completeness of TQBF
Week 9: 10/16-10/20
Readings: Section 4.2
- PSPACE-completeness of TQBF
- Savitch's Theorem, PSPACE = NPSPACE
- Implicitly logspace computable functions, logspace reductions, NL-completeness
Week 10: 10/23-10/27
Readings: Section 4.2, Section 5.1
- Transitivity of logspace reductions and other properties
- PATH is NL-complete
- Certificate definition of NL
- Introduction to the polynomial hierarchy
Week 11: 10/30-11/3
Readings: Sections 5.1 and 5.2
- 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
Week 12: 11/6-11/10
Readings: Section 5.5
- Oracle Turing Machines
- Alternate definition the polynomial hierarchy using oracle TMs.
Week 13: 11/13-11/17
Readings: Sections 6.1, 6.2, and 6.3
- Introduction to circuit complexity, circuit families, and the class
- 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
Week 14: 11/27-12/1
Readings: Theorem 6.19 and its proof, Section 7.1
- 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
- Introduction to randomized computation, the class BPP, examples of randomized algorithms: randomized median finding
Week 15: 12/4-12/8
Readings: Sections 7.3, 7.4, and 7.5
- 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