Популярное видео

Новые поступления

Для просмотра файлов Вам могут потребоваться

International Workshop on Logic and Complexity in Computer Science (LCCS'2001)
5 сентября 2001 г. 09:00, Créteil

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
Real Video 146.4 Mb
Windows Media 154.6 Mb
Flash Video 239.0 Mb
MP4 239.0 Mb
Adobe PDF 66.6 Kb
Adobe PDF 866.9 Kb

Количество просмотров:
Эта страница:520

A. A. Razborov

Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке

Аннотация: 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 $m$ pigeons to $n$ holes when $m>n$) is probably the most extensively studied combinatorial principle in proof complexity. It is amazingly simple and at the same time captures one of the most basic primitives in mathematics and Theoretical Computer Science (counting). Respectively, beginning with the classical paper by Haken (1985), much effort has been put in understanding its proof complexity.
Surprisingly, the complexity of the pigeonhole principle essentially depends on the number of pigeons $m$ (as the function of the number of holes $n$) and on subtle details of its representation as a propositional tautology. This leads to a rich structural picture, and several results obtained during the last couple of years make valuable additions to it.
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.

Материалы: v152_1.pdf (66.6 Kb), v152_2.pdf (866.9 Kb)

Язык доклада: английский

ОТПРАВИТЬ: FaceBook Twitter Livejournal
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018