Introduction to Concrete Complexity

Module aims

[Formerly "Methods and Tools in the Theory of Computing"]

Can we find solutions to problems as quickly as we can identify the correctness of their solutions once given to us? Does every valid formula have short proofs? Are there functions that are easy to compute but hard to invert? These and similar questions such as the P versus NP problem, are the fundamental hardness questions of computer science, which lie at the heart of both the theory and practice of computing. In this module, you will learn some of the major approaches developed to tackle these questions. We shall focus on elementary tools, methods and results: the combinatorial method, through circuit complexity, and the logical approach, through proof-complexity.

Learning outcomes

Upon successful completion of this module, you will be able to:
- Prove fundamental properties of Boolean circuits and their size-complexity.
- Estimate the Boolean circuit size required to compute certain functions using elementary probabilistic techniques.
- Analyse the proof-complexity of certain propositional proof systems.

Module syllabus

Models:
    - The Boolean Circuit model
    - Shannon lower bounds: most Boolean functions require large circuits
    - Connections between circuits and the classes P, NP and Turing machines
    - Propositional proof systems
    - Cook's programme to separate P from NP
Tools:
    - The random restriction method & switching lemmas
    - Constant depth circuit lower bounds
    - Resolution lower bounds for the Pigeonhole Principle
    - The Approximation method: monotone circuits lower bounds for deciding graph cliques

Teaching methods

The material will be taught through lectures and tutorial sessions. Full lecture notes of the material are supplied. You will be assigned unassessed exercises designed to reinforce the material as it is taught. Approximately half of these exercises will be discussed in class or tutorials; the remainder are intended for self-study.

An online service will be used as a discussion forum for the module.

Assessments

There will be one written coursework that contributes 20% of the mark for the module. There will be a final written exam, which counts for the remaining 80% of the marks.

Written and verbal feedback will be given on the assessed coursework.

Reading list

Core Reading

Supplementary Reading

Module leaders

Professor Iddo Tzameret

Reading List

View the module reading list (Leganto)