• 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 L-tautologies is closed under substitution instances of the rule. We are particularly interested in the set-up 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 well-behaved 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.
    • 27.05.19   13:00
    • 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.
    • 20.05.19   13:00

    Pavel Pudlak, Neil Thapen