Non-determinism in Gdels System T
The calculus T ? is a successor-free version of Gdels T. It is well known that a number of important complexity classes, like e.g. the classes logspace, \(\mbox{\sc p}\), \(\mbox{\sc linspace}\), \(\mbox{\sc etime}\) and \(\mbox{\sc pspace}\), are captured by natural fragments of T ? and related calculi. We introduce the calculus T ?, which is a non-deterministic variant of T ?, and compare the computational power of T ? and T ?. First, we provide a denotational semantics for T ? and prove this semantics to be adequate. Furthermore, we prove that \(\mbox{\sc linspace}\subseteq \mathcal {G}^{\backsim }_{0} \subseteq \mbox{\sc nlinspace}\) and \(\mbox{\sc etime}\subseteq \mathcal {G}^{\backsim }_{1} \subseteq \mbox{\sc espace}\) where \(\mathcal {G}^{\backsim }_{0}\) and \(\mathcal {G}^{\backsim }_{1}\) are classes of problems decidable by certain fragments of T ?. (It is proved elsewhere that the corresponding fragments of T ? equal respectively \(\mbox{\sc linspace}\) and \(\mbox{\sc etime}\).) Finally, we show a way to interpret T ? in T ?.
non-determinism gdels system t denotational semantics complexity theory