School of Computing
Queen's University

CISC462 COMPUTABILITY AND COMPLEXITY

Course Description - Fall 2018

Textbook Lecture Topics Course Description Assignments and Tests Grading


NEWS

Nov. 27
Office hours before the exam:

Nov. 21

Nov. 16
In class on Monday Nov. 19 we discuss the timing of the tutorial for the final exam. The tutorial will be scheduled for Dec. 3, 4, or 5, based on a poll we conduct in class on Monday.

Nov. 14
Marked assignment 3 papers will be returned in class tomorrow Thursday. Comments from the TA have been posted on the assignments page.

Nov. 7
Assignment 4 has been posted on the assignments page. Assignment 4 is due in class on Monday November 26.

Announcements concerning the course will be posted above. Please check this page regularly.

Old announcements


Lecture times

Slot 2 Monday 9:30 Wednesday 8:30 Thursday 10:30

Meeting in room Jeffery Hall 101.

Instructor


Teaching Assistant


Textbook

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.

The textbook is available at the Queen's bookstore.


Lecture Topics

The course covers Part 2 and Part 3 of the textbook. Some concepts from Part 1 are reviewed.

Tentative schedule:

Topics Textbook chapter/section Notes outline Week (tentative)
Some history (Godel and Turing); Basics of Turing machines; Computability vs. Complexity
For fun: A nice mechanical/optical 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
Turing machines; Extensions of TMs; Church-Turing thesis Ch. 3 Turing machines Weeks 1, 2
Decidability and undecidability; Review of formal languages concepts; Halting problem; Diagonalization; Universal TMs 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
Mapping reducibility
Weeks 5, 6
Time bounded computations; Polynomial time; Classes P and NP; Time bounded reductions; NP-completeness Ch. 7 Time complexity
The class NP
Weeks 7, 8
Space bounded computations; Class PSPACE; Logarithmic space 8.1 - 8.4 Space complexity
Logarithmic space
Weeks 9, 10
Completeness; 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) Circuit complexity Week 11
Selected advanced topics; Review 10.? - 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.


Course Description

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.

  1. 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 fine, already for input polynomials of small size, to use more time than the age of the universe. However, it is known that there does not exist any (arbitrarily inefficient) algorithm solving the above problem. 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.

  2. 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.

  3. 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 studied.

    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.

    Also everyday experience with computers and programming suggests the following (S. Wolfram):

    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 $1 million USD.


Prerequisites and Academic Policies

Learning outcomes can be found at http://www.cs.queensu.ca/students/undergraduate/CLO.php#CISC462.

Information on Faculty of Arts and Science policies on Academic integrity, accommodations and copyright can be found at http://www.cs.queensu.ca/students/undergraduate/syllabus/ and www.queensu.ca/artsci/sites/default/files/academic_regulations.pdf.


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: PDF Due: Thursday Sept. 27 Solution Comments from the TA
Assignment 2: PDF Due: Thursday October 11 Solution Comments from the TA
Assignment 3: PDF Due: Monday November 5 Solution Comments from the TA
Assignment 4: PDF Due: Monday November 26 Solution Comments from the TA

Concerning the assignments:

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.

Grading

Your grade is calculated as follows:

4 assignments: 40%
Midterm exam: 20%
Final exam: 40%
Total: 100%

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 scale.