The course maps connections between mathematical logic and computational complexity theory.
Last update: T_KA (21.05.2009)
Přednáška probírá souvislosti mezi matematickou logikou a teorií výpočetní složitosti.
Literature -
Last update: T_KA (12.05.2009)
J.Krajíček, Bounded arithmetic, propositional logic, and complexity theory, Cambridge University Press, (1995).
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.
Last update: T_KA (12.05.2009)
Základní pojmy výpočetní složitosti. Definovatelnost predikátu v logice prvního řádu a jejich složitost.Základy teorie konečných modelů. Splnitelné výrokové formule a tautologie. Důkazové systémy pro výrokovou logiku.