Logika a složitost - NALG128

• Anglický název: Logic and complexity
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2013 do 2013
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: nevyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Další informace: http://www.karlin.mff.cuni.cz/~krajicek/ls.html
• Garant: prof. RNDr. Jan Krajíček, DrSc.
• Kategorizace předmětu: Matematika > Algebra
• Záměnnost : NMAG446
• Je neslučitelnost pro: NMAG446
• Je záměnnost pro: NMAG446

Anotace

čeština

Poslední úprava: T_KA (21.05.2009)

Přednáška probírá souvislosti mezi matematickou logikou a teorií výpočetní složitosti.

angličtina

Poslední úprava: T_KA (12.05.2009)

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

Literatura

čeština

Poslední úprava: T_KA (12.05.2009)

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

Sylabus

čeština

Poslední úprava: 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.

angličtina

Poslední úprava: 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.