CISC 462 — Computability and Complexity (Winter 2017)

General information

Timothy Ng (, Goodwin Hall 235
Office hours: Monday 3:30-4:30, Thursday 4:30-5:30
Teaching assistant
Daniel Gotsch (
Office hours: Wednesday 11:00-12:00, Goodwin Hall 235
Botterell Hall B148, Slot 21 (Monday 2:30-3:30, Tuesday 4:30-5:30, Thursday 3:30-4:30)
Michael Sipser. Introduction to the Theory of Computation, 3rd ed.
The textbook is available in the bookstore. Older editions are fine.
10% × 5 assignments + 20% midterm + 30% final
Course webpage

Official course description

Turing machines and other models of computability such as M-5-recursive functions and random-access machines. Undecidability. Recursive and recursively enumerable sets. Church-Turing thesis. Resource-bounded complexity. Complexity comparisons among computational models. Reductions. Complete problems for complexity classes.

CISC 223


The course will cover topics from Parts 2 and 3 of the textbook. This outline is subject to change.

References to the textbook are given simply as section numbers. References to secondary sources are given as section numbers preceded by:

Jan 9
Introduction. What is computability? What is complexity?
Jan 10
Turing machines, decision problems (3.1, 3.2)
Jan 12
Variants of Turing machines, the Church-Turing thesis (3.2, 3.3)
Jan 16
Decidability, properties of regular languages (4.1)
Jan 17
Properties of context-free languages (4.1)
Jan 19
Undecidability, the Universal Turing machine, diagonalization (4.2)
Jan 23
More diagonalization, unrecognizability (4.2)
Jan 24
Undecidable problems (5.1)
Assignment 1 due.
Jan 26
Rice's theorem, Mapping reducibility (5.3)
Jan 30
More reducibility (5.3), linear bounded automata (5.1)
Jan 31
Computation histories (5.1)
Feb 2
Post Correspondence Problem (5.2)
Feb 6
Introduction to complexity, time complexity. (7.1, Aar4)
Feb 7
P. (7.2)
Assignment 2 due.
Feb 9
NP. (7.3)
Feb 13
NP-completeness. (7.4)
Feb 14
Midterm review.
Feb 16
Feb 20: Reading Week
No classes.
Feb 27
NP-complete problems and reductions. (7.5)
Feb 28
More NP-complete problems and reductions. (7.5, AB2.2)
Mar 2
The Cook-Levin theorem. (7.4)
Mar 6
coNP, space complexity (8.1, AB2.6)
Mar 7
PSPACE and Savitch's Theorem. (8.2)
Assignment 3 due.
Mar 9
PSPACE-completeness, logarithmic space (8.3, 8.4)
Mar 13
NL-completeness. (8.5)
Mar 14
NL = coNL. (8.6, AB4.3)
Mar 16
NL-complete problems and reductions.
Mar 20
The space hierarchy. (9.1)
Mar 21
The time hierarchy. (9.1)
Assignment 4 due.
Mar 23
Relativization. (9.2)
Mar 27
The Polynomial Hierarchy. (AB5.1, 5.2, 5.5)
Mar 28
Circuits. (9.3, AB6.1, 6.3, 6.4)
Mar 30
Probabilistic computation. (10.2, AB7.2-7.4)
Apr 3
Derandomization. (AB7.5, Aar7)
Apr 4
Final review.
Assignment 5 due.
Apr 6
No class. (Creative Computing Showcase)


There will be 5 assignments. Assignments are to be done individually. Assignments are to be handed in at the beginning of class in class on the due date. Late assignments will not be accepted. If you are unable to finish the assignment, please discuss the matter with me before the assignment is due, as soon as possible. If approved, the weight of the assignment will be transferred to the following exam (midterm or final).

Assignment 1
Due Jan 24
Assignment 2
Due Feb 7
Assignment 3
Due Mar 7
Assignment 4
Due Mar 21
Assignment 5
Due Apr 4


The midterm will be held on Thursday February 16, in class. It will cover everything on computability theory (Chapters 3 to 5).

This is a closed-book test. You may bring one (1) standard letter size (8.5" x 11") sheet of notes and use it during the test.


The final will be held on Monday April 17 at 9:00 am in Goodwin 247. You will have 3 hours to complete the final. It will cover topics in complexity theory (Chapters 7 to 10).

This is a closed-book test. You may bring one (1) standard letter size (8.5" x 11") sheet of notes and use it during the test.

Academic integrity

Academic Integrity is constituted by the five core fundamental values of honesty, trust, fairness, respect and responsibility (see These values are central to the building, nurturing and sustaining of an academic community in which all members of the community will thrive. Adherence to the values expressed through academic integrity forms a foundation for the "freedom of inquiry and exchange of ideas" essential to the intellectual life of the University (see the Senate Report on Principles and Priorities).

Students are responsible for familiarizing themselves with the regulations concerning academic integrity and for ensuring that their assignments conform to the principles of academic integrity. Information on academic integrity is available in the Arts and Science Calendar (see Academic Regulation 1), on the Arts and Science website, and from the instructor of this course. Departures from academic integrity include plagiarism, use of unauthorized materials, facilitation, forgery and falsification, and are antithetical to the development of an academic community at Queen's. Given the seriousness of these matters, actions which contravene the regulation on academic integrity carry sanctions that can range from a warning or the loss of grades on an assignment to the failure of a course to a requirement to withdraw from the university.


Queen's University is committed to achieving full accessibility for persons with disabilities. Part of this commitment includes arranging academic accommodations for students with disabilities to ensure they have an equitable opportunity to participate in all of their academic activities. If you are a student with a disability and think you may need accommodations, you are strongly encouraged to contact Student Wellness Services (SWS) and register as early as possible. For more information, including important deadlines, please visit the Student Wellness website at: