Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (17.05.2019)
Základní kocepty teorie výpočetní složitosti. Definovatelnost v logice prvního řádu. Konečná teorie modelů. Důkazová složitost a SAT algoritmy, Herbrandova věta a dosvědčující věty.
Poslední úprava: 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.
Vstupní požadavky -
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (17.05.2019)
Základní znalosti matematické logiky.
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (17.05.2019)