Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 336)
Detail práce
   Přihlásit přes CAS
Algebraické důkazové systémy
Název práce v češtině: Algebraické důkazové systémy
Název v anglickém jazyce: Algebraic proof systems
Akademický rok vypsání: 2006/2007
Typ práce: diplomová práce
Jazyk práce: angličtina
Ústav: Katedra algebry (32-KA)
Vedoucí / školitel: prof. RNDr. Jan Krajíček, DrSc.
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 07.12.2006
Datum zadání: 07.12.2006
Datum a čas obhajoby: 01.06.2009 00:00
Datum odevzdání elektronické podoby:20.04.2009
Datum odevzdání tištěné podoby:20.04.2009
Datum proběhlé obhajoby: 01.06.2009
Oponenti: prof. RNDr. Pavel Pudlák, DrSc.
 
 
 
Zásady pro vypracování
Popsat důkazový systém pro výrokovou logiku založený na algebře a porovnat jeho sílu s obvyklými výrokovými počty.
Seznam odborné literatury
S.Buss, R.Impagliazzo, J.Krajicek, P.Pudlak, A.A.Razborov a J.Sgall, Proof complexity in algebraic systems and bounded depth Frege systems with modular counting, Computational Complexity, 6(3), str.256-298, (1996/97).

S.Cook a R.Reckhow, The relative efficiency of propositional proof systems, J. of Symbolic Logic, 44(1), str.36-50, (1979).

J.Krajicek: Bounded arithmetic, propositional logic, and complexity theory, Cambridge U. Press, (1995).

J.Krajicek, Dehn function and lengths of proofs, Int.J. of Algebra and Computation, 13(5), str.525-542, (2003).
Předběžná náplň práce
Obecný pojem výrokového důkazového systému (definován Cookem a Reckhowem) zobecňuje obvykle výrokové počty. Některé z těchto systemů používají algebru (např. Nullstellensazt). Úkolem práce je nějaký takový algebraický systém definovat a porovnat jeho sílu s obvyklým výrokovým počtem.
Předběžná náplň práce v anglickém jazyce
The general notion of a propositional proof system (defined by Cook and Reckhow) generalizes usual propositional calculi. Some of these systems are based on algebra (e.g. Nullstellensatz). The goal of the project is to describe some such system and compare its strength with the strength of the usual text-book calculus.
 
Univerzita Karlova | Informační systém UK