Topics
So far we have only been concerned with which problems can be solved
in theory, i.e., whether there exists an algorithm that solves
a given problem given unbounded memory and execution time. However,
although such problems can be solved in some theoretical sense, in
many cases it is too time or space demanding to find their solutions.
The aim of complexity theory is to investigate the amount of
resources that are needed to solve decidable problems, and thus to
what extent decidable problems can be solved in practice.
In this lecture, I shall give you a taste of basic complexity
theory. We shall focus on time complexity, and shall begin by
reviewing the basic methodology for measuring the time efficiency of
algorithms. We shall then introduce the complexity class P, and
present examples of problems that belong to it. According to the
"Cook-Levin thesis", the complexity class P is invariant under
"reasonable models of computation", and is taken to consist of the
class of decision problems that are "efficiently solvable".
Time and Location
Monday, 18 October, 2004 at 10:15 in A4-106.
Reading Material
Material in pages 225-241 of Sipser's book.
Exercises
Work out exercises 7.1.(a-d) and e(*), 7.4(*), 7.6(*),
7.8, 7.9, 7.10(*) on pp. 271-272 of
Sipser's book.
Luca Aceto,
Department of
Computer Science,
Aalborg University.
Last modified: