I'll give a brief introduction to systems of second-order arithmetic and the study of their proof-theoretic ordinals. Further the focus will be on well-ordering principles and the approach to ordinal analysis based on functorial ordinal notation systems.
Logic seminar
usually takes place each Monday at 16:00 in IM, rear building, ground floorChair: Pavel Pudlak, Neil Thapen, Jan Krajíček
More information on the old seminar web page. The programme is announced via the mailing list.
Systems of second order arithmetic and well-ordering principles, Part 3
Fedor Pakhomov
Institute of Mathematics
Monday, 9. December 2019 - 13:30 to 15:00
Systems of second order arithmetic and well-ordering principles, Part 2
Fedor Pakhomov
Institute of Mathematics
Monday, 2. December 2019 - 13:30 to 15:00
I'll give a brief introduction to systems of second-order arithmetic and the study of their proof-theoretic ordinals. Further the focus will be on well-ordering principles and the approach to ordinal analysis based on functorial ordinal notation systems.
Automating Resolution Is NP-Hard
Albert Atserias
Universitat Politècnica de Catalunya
Monday, 25. November 2019 - 13:30 to 15:00
We show that the problem of finding a Resolution refutation that is at most polynomially longer than a shortest one is NP-hard. In the parlance of proof complexity, Resolution is not automatizable unless P = NP. Indeed, we show that it is NP-hard to distinguish between formulas that have Resolution refutations of polynomial length and those that do not have subexponential length refutations. This also implies that Resolution is not automatizable in subexponential time or quasi-polynomial time unless NP is included in SUBEXP or QP, respectively.
This is joint work with Moritz Müller
This is joint work with Moritz Müller
Systems of second order arithmetic and well-ordering principles
Fedor Pakhomov
Institute of Mathematics
Monday, 18. November 2019 - 13:30 to 15:00
In the present talk I'll give a brief introduction to systems of second-order arithmetic and the study of their proof-theoretic ordinals. Further the focus will be on well-ordering principles and the approach to ordinal analysis based on functorial ordinal notation systems.