School of Computing
CISC462 COMPUTABILITY AND COMPLEXITY
Course Description - Fall 2018
Announcements concerning the course will be posted above.
Please check this page regularly.
- Sept. 10
- Assignment 1 has been posted
on the assignments page.
Assignment 1 is due in class on September 27.
- Sept. 10
- The office hours have been posted. The office hours begin
the week of Sept. 17.
- Sept. 3
- Welcome to the course!
|| Wednesday 8:30
Meeting in room
Jeffery Hall 101.
- Kai Salomaa
- Goodwin 545, 533-6073
- ksalomaa at cs dot queensu dot ca
- Office hour: Tuesday 12:30 - 1:30 PM Goodwin 545
You can drop by my office also at other times when I'm around.
If you prefer to make an appointment,
please talk with me after class.
- Taylor Smith
- tsmith at cs dot queensu dot ca
- Office hour: Wednesday 2:30 - 3:30 PM, Goodwin 241. (The TA office
hours begin the week of Sept. 17.)
You may be able to find a used copy of the second
or the first edition
of the textbook
Introduction to the Theory of Computation by Michael Sipser.
The earlier editions should be usable but may
differ slightly from
the current edition.
The first edition has fewer exercises.
textbook is available at the Queen's bookstore.
The course covers Part 2 and Part 3 of the
Some concepts from Part 1 are reviewed.
Some history (Godel and Turing);
Basics of Turing machines; Computability vs. Complexity
For fun: A nice
Turing machine implementation. (Strictly speaking, the implementation is only
what we will call a linear bounded automaton.)
| Ch. 3
Introduction: history and motivation
|| Week 1
Extensions of TMs;
|| Weeks 1, 2
Decidability and undecidability;
Review of formal languages concepts;
Halting problem; Diagonalization;
|| Ch. 4
Parts of Ch. 1 and 2
Decidability and undecidability
|| Weeks 3, 4
|Establishing unsolvability using reductions;
PCP; Rice's theorem
|| Ch. 5
Further undecidable problems
| Weeks 5, 6
|Time bounded computations; Polynomial time;
Classes P and NP; Time bounded reductions; NP-completeness
|| Ch. 7
The class NP
| Weeks 7, 8
|Space bounded computations; Class PSPACE;
|| 8.1 - 8.4
| Weeks 9, 10
Relationships between complexity classes;
Time and space hierarchy
|| 8.5, 8.6, 9.1
Space and time hierarchies
|| Week 10
Circuit complexity; Oracles and Turing reductions
|| 9.2, 9.3, (6.3)
|| Week 11
|Selected advanced topics; Review
|| Week 12
Note: The posted notes are only an outline
and are intended to assist in taking notes in class. The posted notes
are not a replacement for the classes.
The objective of the course is to provide an introduction
to computability and complexity,
which are part of the
theory of algorithms.
The notion of an algorithm is fundamental in
computer science, however algorithms have been
studied much before the invention of modern
computers. One of the oldest and, perhaps, most
well known algorithms, Euclid's algorithm to compute the
greatest common divisor, is over 2000 years old. The term
"algorithm" comes from the Persian mathematician
Mohammed-al-Kwowarizmi (9th century).
The theory of algorithms, as a topic of its own,
was born only in the last century, in particular the
second half of it. There are three rather
separated directions in this research.
- Computability (which is sometimes called
recursive function theory) studies which problems
are in principle algorithmically decidable, that is,
solvable by a computer.
This research got started when Kurt Goedel proved that there
exist algorithmically unsolvable problems.
Goedel's results were formulated in terms of logical theories
but later many concrete and quite innocent looking problems have
been shown to be unsolvable.
For example, there is no general algorithm that
determines whether or not a polynomial equation with integer
coefficients has a solution among the integers.
Note that here we are not (yet) in any way concerned with
resources used by the algorithm. For such an algorithm it would be completely
already for input polynomials of small size,
more time than the age of the universe.
it is known that there does not exist
any (arbitrarily inefficient) algorithm solving the above
This question is the so called Hilbert's tenth problem
and its unsolvability was established by Yuri Matiyasevich in 1970.
Computability theory studies and classifies nonrecursive
(unsolvable) problems, and in this classification the solvable
problems form only a single (lowest) class.
- Theory of designing and analysing algorithms:
Another direction arose in connection with the fast development
of computers, starting in the 50's. It became clear that recursive
problems requiring centuries of computer time for solving
instances with small input data, were too difficult to be
considered solvable in practice.
This approach concentrates on developing fast computer
algorithms and methods to analyse those.
- Classifications of complexities of problems:
The third direction lies in-between the first two areas.
In the 60's it was generally accepted that the class
of "feasible" algorithms consists of algorithms that require
computation time polynomial in the size of the input.
(This classification is only an approximation and it
has its own problems, as will
be discussed during the course.) Polynomial time reductions
were defined, and relationships between complexity classes
and complete problems for the classes began to be
Thus we should distinguish the notions:
The complexity of an algorithmic problem is the complexity
of the "best" (with respect to some resource measure)
algorithm solving this problem.
- complexity of an algorithm;
- complexity of an algorithmic problem.
Also everyday experience with computers
and programming suggests the following (S. Wolfram):
- The solution to a given algorithmic problem can be implemented
in many ways.
- It is often difficult to foresee what a program can do
by reading its code.
- Programs (even very simple ones) can behave in complicated
and seemingly random ways - particularly when they are not working
The task of determining the complexity of a given
algorithm is often (but not always) a manageable
problem. On the other hand, the task of determining
the complexity of a given algorithmic problem is usually
very difficult (hopeless). As we will see,
the exact relationships of even the fundamental and most studied
complexity classes (P, NP, PSPACE, LOGSPACE,...) remain
unknown. If you are able to solve the
"P versus NP" problem you will immediately get
Prerequisites and Academic Policies
outcomes can be found at
- CISC 223
- CISC 365 is useful, but not required
Information on Faculty of Arts and Science policies on Academic integrity,
accommodations and copyright can be found at
Assignments and Tests
There will be 4 written homework assignments, a midterm test
and a final exam.
Assignment due dates:
Each assignment has a weight of 10% for your total grade.
The assignments are due at the beginning of the class on the due date.
| Assignment 1:
||Due: Thursday Sept. 27
| Assignment 2:
||Due: Thursday October 11
| Assignment 3:
||Due: Monday November 5
| Assignment 4:
||Due: Monday November 26
Concerning the assignments:
- The assignments are due at the begin of class on the
- The assignments must be submitted in paper copy. Assignments
sent by email are not accepted.
- Late assignments:
Late assignments will be accepted up to two days (48 hours) after the
time they are due.
Assignments that are more than 48 hours late are not accepted.
- The penalty for a late assignment is 10% of the maximum mark.
- If you miss an assignment due to illness or similar reason,
you should discuss the matter with the instructor before
the assignment due date. If the instructor accepts the reason,
we will use your midterm test mark to replace a missed assignment 1 or 2,
or your final exam mark to replace a missed assignment 3 or 4.
- If you have questions concerning assignment marking, you should
discuss them with the teaching assistant within one week
from the time when the marked assignments are made available.
All assignment marks are considered final after that time.
- Academic integrity:
All assignments must be based on individual work.
You are permitted to discuss
general aspects of the assignment problems with your fellow students
but you should
enter and leave from such discussions without any written notes.
The written solution you hand in must be created completely
independently by you. You are of course free to discuss the
assignment problems with the instructor or the
- Please see a
Integrity from the Arts and Science
web site posted at
Midterm and Final Exam
There will be a 50 minute closed book midterm test
held during the class hour and
a 3 hour closed book final exam.
- Midterm test time: Thursday October 18, 10:30 AM.
- The final exam
will be scheduled during the December final examination period.
- The midterm and the final are closed-book exams. You may bring
standard size 8.5" x 11" sheet containing notes to each test
and use it during the test. The sheet can be written/printed on
is calculated as follows:
- If you do better on the final exam than on the midterm, we will
replace your midterm mark by the final exam mark (as a percentage).
Note: The components of this course will receive numerical marks
that will be used to calculate a percentage final grade, as
explained above. The final grade you receive for the course
will be derived by converting your percentage grade to
a letter grade according to Queen's official grade conversion