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.
- zadáno a potvrzeno stud. odd.