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 2024
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:	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.
Teacher(s):	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 Noticeboard

Annotation -

The course maps connections between mathematical logic and computational complexity theory. The course may not be taught every academic year.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (31.05.2019)

Course completion requirements

Oral exam.

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

Literature -

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

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

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

Syllabus -

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.

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

Entry requirements -

Basic knowledge of matematical logic.

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