The seminar originally planed to study this semester bounded arithmetic,
reading selected material from my books:
Bounded arithmetic,
propositional logic, and complexity theory,
Cambridge U. Press, 1995.
(starting with Chpt.5)
Proof Complexity, Cambridge U. Press, 2019.
(selected from Part 2 there)
and from
Steve Cook and Phuong Nguyen:
Foundations of Proof Complexity: Bounded
Arithmetic and Propositional Translations,
a draft of a book.
But we had to give that up:
Topic for the corona-virus induced break from March 11 onwards
To proceed in our seminar during the closure of the university
according to the original plan but "on distance" would
not work very well: the material contains
a lot of new definitions, some lengthy arguments and a number of different
things are put together to form the "big picture", and that
is hard to discuss or present online.
But to keep the fire burning we started to work our way through
a series of problems about theory I\Delta_0 (which we know already
reasonably well) and the provability of various versions
of PHP there. These problems ought to lead us in few weeks
to some of the deepest topics in this area and in the adjacent
area of proof complexity, and we plan to eventually
make it towards (understanding of) some of the most famous open
problems in the area.
Problems 1, 2 and 3.
Solution of Problem 1 (L.Folwarczny).
Notes for Problems 2 and 3: 1st notes
and 2nd notes.
Problem 4.
Solution (O.Jezil and M.Narusevych) and
notes with answers to their questions.
Problem 5
and its solution.
Problem 6
and its solution.