Computational Complexity

In this course we will give a thorough and self-contained introduction to the area of computational complexity theory. Starting off from the abstract computational model of a Turing machine, we will discuss deterministic and non-deterministic time- and space complexity classes with regard to their structural and algorithmic properties. We will address numerous relevant examples while putting some emphasis on the complexity classes P and NP as well as to the theory of NP-completeness.

Some keywords: dynamic complexity measures; deterministic and nondeterministic polynomial time; the P versus NP problem and its relativization, NP completeness; die polynomial hierarchy and PSPACE.

Details

Code 41026
Type Course
ECTS 5
Site Bern
Track(s) T4 – Logic
Semester S2021

Teaching

Learning Outcomes

On successful completion of this course, you will be able to:

  • Classify algorithmic problems into complexity classes
  • Determine the known relationships between complexity classes
  • Show that an algorithmic problem in NP-complete
  • Understand the P versus NP problem
  • Discuss problems whose complexity is beyond NP
  • Understand problems with polynomial space complexity
Lecturer(s) Thomas Strahm
Language english
Course Page

The course page in ILIAS can be found at https://ilias.unibe.ch/goto_ilias3_unibe_crs_1841373.html.

Schedules and Rooms

Period Weekly
Schedule Tuesday, 14:15 - 17:00
Location UniBE, ExWi

Additional information

Comment

First Lecture
The first lecture will be announced later.