- Institute
- People
- Departments
- Algebra, Geometry and Mathematical Physics (AGMP)
- Branch in Brno (BB)
- Constructive Methods of Mathematical Analysis (CMMA)
- Didactics of Mathematics (DM)
- Evolution Differential Equations (EDE)
- Mathematical Logic, Algebra and Theoretical Computer Science (MLATCS)
- Topology and Functional Analysis (TFA)
- Archive of departments
- Positions
- Research
- Events
- Calendar
- Partnerships
- Links
Logic seminar
On the parameterized complexity of Delta-0 truth
Moritz Müller
University of Passau
Monday, 21. November 2022 - 16:00 to 17:30
Online - https://cesnet.zoom.us/j/472648284 - contact thapen@math.cas.cz before the meeting to join
We consider the problem, given a Δ0 formula φ(x) and a natural number n in unary, whether φ(n) is true. We are interested in instances of the problem where n is much bigger than φ. More precisely, we consider the parameterized problem with parameter |φ|. We show unconditionally that this problem does not belong to the parameterized version of AC0. We also show that certain natural upper bounds on the parameterized complexity of the problem imply separations of classical complexity classes. These results are obtained by an analysis of a parameterized halting problem. A related problem concerns the provability of the MRDP theorem in bounded arithmetic.