Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Logic and Complexity - NMAG446

Title:	Logika a složitost
Guaranteed by:	Department of Algebra (32-KA)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2022
Semester:	summer
E-Credits:	3
Hours per week, examination:	summer s.:2/0, Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	not taught
Language:	English, Czech
Teaching methods:	full-time
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
Is interchangeable with:	NALG128

Opinion survey results Examination dates Schedule Noticeboard

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.