Module Number

INFO-4444
Module Title

Complexity Theory II
Lecture Type(s)

Lecture
ECTS 6
Work load
- Contact time
- Self study
Workload:
180 h
Class time:
60 h / 4 SWS
Self study:
120 h
Duration 1 Semester
Frequency Irregular
Language of instruction German
Type of Exam

Oral examination (written exam if there are a large number of participants)

Content

Building on the lecture Complexity Theory, the in-depth topics include (non) uniform circuit classes, approximation theory, and randomization. In addition, barriers in the form of relativization and natural proofs are considered.

Objectives

Students have an overview of different complexity classes, circuits and randomisation and are able to write a master thesis in this field.

Allocation of credits / grading
Type of Class
Status
SWS
Credits
Type of Exam
Exam duration
Evaluation
Calculation
of Module (%)
Prerequisite for participation There are no specific prerequisites.
Lecturer / Other
Literature

-

Last offered unknown
Planned for currently not planned
Assigned Study Areas INFO-INFO, INFO-THEO, MEDI-APPL, MEDI-INFO, ML-CS