|
ВИДЕОТЕКА |
International Workshop on Logic and Complexity in Computer Science (LCCS'2001)
|
|||
|
Proof Complexity of pigeonhole principles A. A. Razborovab a Institute for Advanced Study, School of Mathematics b Steklov Mathematical Institute of Russian Academy of Sciences, Moscow |
|||
Аннотация: Propositional proof complexity is an area of study that has seen a rapid development over a couple of last decades. It plays as important a role in the theory of feasible proofs as the role played by the complexity of Boolean circuits in the theory of efficient computations. After a brief review of general underlying definitions, we will concentrate in this talk on lower and upper bounds describing the complexity of particular tautologies that express various forms of the so-called pigeonhole principle. This principle (asserting that there is no injective mapping from Surprisingly, the complexity of the pigeonhole principle essentially depends on the number of pigeons We will try to summarize what is known about the proof complexity of pigeonhole principles, and what we still would like to prove. If time permits, we will also give some proof details of a new lower bound on the size of resolution proofs of the pigeonhole principle with arbitrarily many pigeons. Язык доклада: английский |