Complexity of computations and proofs and pseudo-finite structures
Krajicek, J (Charles University, Prague)
Monday 26 March 2012, 09:30-10:30
Seminar Room 1, Newton Institute
Abstract
Problems to establish lower bounds for circuit size or for lengths of propositional proofs can be formulated as problems to construct expansions of pseudo-finite structures.
I will explain this relation, give a few examples, and discuss some recent work aimed at proof complexity.
Comments
Start the discussion!