IT-Universitetet i København
  Tilbage Kursusoversigt
Kursusnavn (dansk):Logik og beregnelighed 
Kursusnavn (engelsk):Logic and Computability 
Semester:Efterår 2003 
Udbydes, internet- og softwareteknologi (int) 
Omfang i ECTS:7,50 
Min. antal deltagere:
Forventet antal deltagere:10 
Maks. antal deltagere:30 
Formelle forudsætninger:The students should be able to

  • 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

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.

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.