Original title: Výroková logika a algebra
Translated title: Výroková logika a algebra
Authors: Polach, František ; Krajíček, Jan (advisor) ; Pudlák, Pavel (referee)
Document type: Master’s theses
Year: 2008
Language: eng
Abstract: Algebraic proof systems of which the most important are the polynomial calculus and the Nullstellensatz proof system are proof systems that use algebraic means for proving propositional tautologies - they are based on polynomial identities over (commutative) rings. Razborov [9] have proved a non-trivial lower bound on degree for polynomia calculus proofs of the tautologies (a set of polynomials) that express the pigeonhole principle over any field. This work gathers present important results for algebraic proof systems and generalizes the Razborov's construction used in his proof of the lower bound to another set of polynomials. We explicitly describe the basis of the vector space of polynomials that are derivable by a small degree polynomial calculus proof from the tautologies that express a variant of the pigeonhole principle (that generalizes the principle for multifunctions).

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/17708

Permalink: http://www.nusl.cz/ntk/nusl-294438


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses