Lecture “The proof complexity”. Lecturer: Vsevolod Oparin (St. Petersburg Academic University)
Event ended
On November 2, 2016 Vsevolod Oparin will give a lecture “The proof complexity”.
Time: 16:40 - 18:00
Address: Kochnovsky proezd, 3
Hall: 505
To attend the seminar one should have a pass to the building. If you don’t have a pass please send your contact information (Surname, name) to Ekaterina Vavilova: evavilova@hse.ru .
Abstract
The proof complexity is a part of theoretical computer science that deals with the question “How hard is to prove a particular theorem?” and complexity of the proof is the measure of hardness.
When we talk about complexity, we mean that we have some formal proof system in which we estimate the size of the shortest proof in this system. Answers for questions from this area may shed light on the P versus NP question and also estimate the potential of automatic proof systems of mathematical theorems. Lecture also provides the short review of the whole area.