
Emil Je?ábek

(Institute of Mathematics)

Complexity of admissible rules with parameters
 Abstract:

A rule \phi_1, ..., \phi_k / \psi is admissible in a (nonclassical) propositional logic L if the set of Ltautologies is closed under substitution instances of the rule. We are particularly interested in the setup with parameters (constants), which are required to be preserved by substitutions. In this talk, we shall study basic properties of admissibility with parameters in a class of wellbehaved transitive modal logics (i.e., extensions of K4). The main goal is a classification of the computational complexity of admissibility (and the closely related problem of unifiability) with parameters based on semantic properties of logics.

Pavel Pudlák

(Mathematical Institute)

Propositional proofs and monotone computations
 Abstract:

One of the major discoveries of Stephen Cook is that lower bounds on the lengths of proofs in the propositional calculus can be used to prove independence results. This stimulated research into proving lower bounds for various propositional proof systems. Later it was shown that one can use lower bounds on the size of monotone circuits to prove lower bounds on propositional proofs. New models of monotone computations have been proposed recently that potentially may give us lower bounds for more propositional proof systems that we have so far. In this talk we will survey some results that connect lower bounds on monotone computations in various models with lower bounds on the lengths of proofs in proof systems.
Pavel Pudlak, Neil Thapen
organizers