• work with sets and functions


• work with integer and real numbers


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


• perform mathematical proofs


• be familiar with the concept of programming

• 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.
 

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.
 

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

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