论文标题
IL的封闭片段是pspace硬
The closed fragment of IL is PSPACE hard
论文作者
论文摘要
在2011年的本文中，我们考虑$ \ textbf {il} _0 $，基本的可解释性逻辑$ \ textbf {il} $的封闭片段。我们表明，我们可以将$ \ textbf {gl} _1 $转换为gödel-löb的propabilty逻辑$ \ textbf {gl} $的一个变量片段，为$ \ textbf {il} _0 $。调用$ \ textbf {gl} _1 $的pspace完整性，我们获得$ \ textbf {il} _0 $的pspace硬度。
In this paper from 2011 we consider $\textbf{IL}_0$, the closed fragment of the basic interpretability logic $\textbf{IL}$. We show that we can translate $\textbf{GL}_1$, the one variable fragment of Gödel-Löb's provabilty logic $\textbf{GL}$, into $\textbf{IL}_0$. Invoking a result on the PSPACE completeness of $\textbf{GL}_1$ we obtain the PSPACE hardness of $\textbf{IL}_0$.
