SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Logic and Complexity - NMAG446
Title in English: Logika a složitost
Guaranteed by: Department of Algebra (32-KA)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018 to 2018
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech
Teaching methods: full-time
Additional information:
Guarantor: prof. RNDr. Jan Krajíček, DrSc.
Class: M Mgr. MSTR
M Mgr. MSTR > Povinně volitelné
Classification: Mathematics > Algebra
Incompatibility : NALG128
Interchangeability : NALG128
Annotation -
Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (31.05.2019)
The course maps connections between mathematical logic and computational complexity theory.
Course completion requirements
Last update: prof. RNDr. Jan Krajíček, DrSc. (22.02.2019)

Oral exam.

Last update: prof. RNDr. Jan Krajíček, DrSc. (22.02.2019)

J.Krajicek, Proof complexity, Cambridge U. Press, 2019.

Last update: prof. RNDr. Jan Krajíček, DrSc. (22.02.2019)

Basic concepts of computational complexity theory. Definability in first-order logic. Finite model theory. Proof complexity and SAT algorithms. Herbrand's theorem and witnessing theorems.

Charles University | Information system of Charles University |