School of Computing
Queen's University

COMPUTATIONAL COMPLEXITY CISC-876

Fall 2017


Note: Because of the way the course is offered, at most 20 students can take the course. Until Sept. 20 preference in registration is given to students from the School of Computing.


The goal of complexity theory is to discover and quantify the amount of computational resources required to solve important computational problems and to classify problems as to their intrinsic computational difficulty. Usually the most relevant resources are computational time, space (memory size) and circuit size (hardware). The main challenge is to establish lower bounds, that is, to prove that certain problems cannot be solved without expending large amounts of resources. The P =? NP question is the most famous problem of this type and it has remained unsolved for close to 50 years. For a recent attempted proof see here.

The results of complexity theory have very practical significance. For example, modern public-key cryptography has developed advanced protocols for providing services such as secure user identification or digital cash. The security of a public-key cryptosystem is based on the hardness of some computational problem (there is no efficient algorithm for solving the problem). However, as long as we don't have lower bounds for the complexity of these problems the security of the protocols remains conditional.

Topics

The course discusses the main complexity measures and provides an introduction to some more advanced topics in computational complexity and circuit complexity. Depending on time and interests, we can include a guided tutorial on the limits of algorithmic computation and uncomputability.

Planned topics include:

For more information about the course please contact the instructor.


Meeting times

If you would like to take the course and cannot attend the first class, please contact the instructor before the first class concerning your schedule.


Prerequisites

It is expected that participants are familiar with basic definitions concerning the time/space used by an algorithm (or a Turing machine). These notions will be reviewed in the beginning of the course.

Undergraduate students wishing to take the course should contact the instructor first.


Instructor


Evaluation


Texts

There is no required textbook in the course. I will make printed course notes available. Additionally we may use some research papers.

Supplementary and background reading material for the course can be found in the following texts that are placed on reserve in the Engineering & Science Library.