School of Computing
Queen's University

COMPUTATIONAL COMPLEXITY CISC-876

Fall 2018

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


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 briefly reviewed in the beginning of the course. I will suggest textbooks where you can find more detailed information.

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.