Truth and Feasible Reducibility

Let $\mathcal{T}$ be any of the three canonical truth theories $\textsf{CT}^-$ (Compositional truth without extra induction), $\textsf{FS}^-$ (Friedman--Sheard truth without extra induction), and $\textsf{KF}^-$ (Kripke--Feferman truth without extra induction), where the base theory of $\mathcal{T}$ is $\textsf{PA}$ (Peano arithmetic). We show that $\mathcal{T}$ is \textit{feasibly reducible to} $\textsf{PA}$, i.e., there is a polynomial time computable function $f$ such that for any proof $π$ of an arithmetical sentence $ϕ$ in $\mathcal{T}$, $f(π)$ is a proof of $ϕ$ in $\textsf{PA}$. In particular, $\mathcal{T}$ has at most polynomial speed-up over $\textsf{PA}$, in sharp contrast to the situation for $\mathcal{T}[\textsf{B}]$ for \textit{finitely axiomatizable} base theories $\textsf{B}$.

No reviews yet.

No comments yet.