Non-determinism in Godel's System T

作者：Kristiansen Lars^*; Mender Bedeho Mesghina Wolde

来源：Theory of Computing Systems, 2012, 51(1): 85-105.

DOI：10.1007/s00224-011-9377-9

• Complexity Theory
• Non-determinism
• Godel's System T
• Denotational semantics

The calculus T- is a successor- free version of Gdel's T. It is well known that a number of important complexity classes, like e. g. the classes LOGSPACE, P, LINSPACE, ETIME and PSPACE, are captured by natural fragments of T- and related calculi. We introduce the calculus T-similar to , which is a non-deterministic variant of T-, and compare the computational power of T-similar to and T-. First, we provide a denotational semantics for T-similar to and prove this semantics to be adequate. Furthermore, we prove that LINSPACE subset of G(0)(similar to). NLINSPACE and ETIME subset of G(1)(similar to). ESPACE where G(0)(similar to) and G(1)(similar to) are classes of problems decidable by certain fragments of T-similar to. ( It is proved elsewhere that the corresponding fragments of T- equal respectively LINSPACE and ETIME.) Finally, we show a way to interpret T-similar to in T-.

• 出版日期2012-7