Subjects

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

Logic and complexity - NALG128

Title:	Logika a složitost
Guaranteed by:	Department of Algebra (32-KA)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2018
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:	cancelled
Language:	English
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.
Classification:	Mathematics > Algebra
Interchangeability :	NMAG446
Is incompatible with:	NMAG446
Is interchangeable with:	NMAG446

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

Last update: T_KA (12.05.2009)

The course maps connections between mathematical logic and computational complexity theory.

Literature -

Last update: T_KA (12.05.2009)

J.Krajíček, Bounded arithmetic, propositional logic, and complexity theory, Cambridge University Press, (1995).

Syllabus -

Last update: T_KA (12.05.2009)

Basic concepts of computational complexity theory. Definability of predicates in first-order logic, and their complexity. Elements of finite model theory. Satisfiable propositional formulas and tautologies. Propositional proof systems.