SubjectsSubjects(version: 850)
Course, academic year 2019/2020
   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 2019 to 2019
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: not taught
Language: English, Czech
Teaching methods: full-time
Additional information: http://www.karlin.mff.cuni.cz/~krajicek/ls.html
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. The course may not be taught every academic year.
Course completion requirements
Last update: prof. RNDr. Jan Krajíček, DrSc. (22.02.2019)

Oral exam.

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

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

http://www.karlin.mff.cuni.cz/~krajicek/prfdraft.html

Syllabus -
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.

Entry requirements -
Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (17.05.2019)

Basic knowledge of matematical logic.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html