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:
- Classical complexity classes, P=?NP
- Randomized algorithms and probabilistic complexity classes
- Interactive protocols and zero-knowledge proof systems
- Lower bounds for circuits
- Parallel complexity classes and alternation
- Communication complexity of two-party protocols
- Uncomputability (guided tutorial)
For more information about the course please contact the
instructor.
Meeting times
- Tuesday 2:30 - 4:00 PM Goodwin 521
- Wednesday 2:30 - 4:00 PM Goodwin 521
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
- Three written assignments: 30%. The assignments
must be based on individual work.
- 90 minute closed-book quiz: 15%.
The quiz will be held in class on Tuesday November 27.
The quiz tests understanding
of basic concepts covered in the course. Part of the questions are based
on the assignments.
- Seminar presentation and
research paper: 50%. Each participant is required to
give a seminar presentation in class and write a survey
paper on the same topic. I will suggest several
possible topics for the presentations.
Alternatively, you are welcome to suggest
your own favorite complexity theory topic for the presentation.
- Class participation 5%. Active discussion and questions
during lecture are encouraged. However, you will get
the full participation mark as long as you attend all the lectures.
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.
- J.L. Balcazar, J. Diaz, J. Gabarro: Structural Complexity I,
Springer-Verlag, 1995
- C.H. Papadimitriou: Computational Complexity, Addison-Wesley,
1994
- U. Schoning, R. Pruim: Gems of Theoretical Computer Science,
Springer-Verlag, 1998
- M. Sipser: Introduction to the Theory of Computation,
Thomson, 1997
