Characterising Complexity Classes by Fixed Point Axioms

Naohi Eguchi

(University of Innsbruck)

Any terminating computation can be understood via the fixed point of an operator since once it reaches the accepting state, the configuration of an underlying machine model no longer changes. In finite model theory, it is known that every polynomial-time predicate can be expressed by the first order predicate logic with the fixed point predicate of a monotone operator whereas every polynomial-space predicate can be expressed by the first order predicate logic with the
fixed point predicate of a non-monotone operator. We introduce a fixed point axiom over a weak fragment of Peano
arithmetic, which is known as bounded arithmetic, providing new characterisations of polynomial-time/-space functions.
Thursday 19th September 2013, 14:00
Robert Recorde Room
Department of Computer Science