be familiar with the rates of growth of functions (big O, ?, ?);

perform mathematical proofs

be familiar with the concept of programming

At IT-C, these prerequisites can be picked up at the courses Introduction to Algorithms and Data Structures and/or IT-mathematics.

Læringsmål:

After the course the students should be able to

verify validity of propositional and 1st order formulas;

<!--

prove completeness theorems for propositional and 1st order logic;

-->

construct models of 1st order languages and 1st order theories;

construct models with prescribed properties;

<!--

apply quantifier elimination techniques;

-->

distinguish between decidable and undecidable problems;

<!--

construct key examples of sets and functions with extremal algorithmic properties;

-->

evaluate the complexity of algorithmic problems;

construct reductions between algorithmic problems.

Fagligt indhold:

The subjects of logic, computability, and complexity are inherently intertwined. This becomes already apparent from a glance at the history: The very first examples of NP-complete, PSPACE-complete, as well as other key examples of problems with extremal algorithmic properties, came from logic (propositional, 1st order, as well as other kinds thereof). Today, capturing complexity classes with particular variations of logical languages is an increasingly popular pastime.

Complexity theory creates an appropriate framework for, among other things, the question How complex is a given algorithmic problem? (as opposed to how complex an individual algorithm for solving that problem is), and in many important situations, provides a satisfyingly precise answer to this question.

This course will offer a reasonably comprehensive introduction to logic, computability, and complexity. In particular, we intend to cover the following topics:

basic logical calculi;

models and theories;

Turing machines;

NP-complete problems;

complexity-theoretic classifications of algorithmic problems;

elements of recursion theory;

Gödel incompleteness.

Læringsaktiviteter:

6 x 45 minutes a week worth of freely interleaved lectures, discussions, and exercises.

Eksamensform og -beskrivelse:

X. experimental examination form (7-scale; external exam), 13-skala, Ekstern censur

At the (4-hour) exam, students will be offered a collection of small problems of theoretical nature.

Litteratur udover forskningsartikler:

C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 0-201-53082-1.