The Structure of Detour Degrees

摘要

We introduce a new subrecursive degree structure: the structure of detour degrees. We provide definitions and basic properties of the detour degrees, including that they form a lattice and admit a jump operator. Our degree structure sheds light upon the open problems involving the small Grzegorcyk classes. There are also connections to complexity theory and complexity classes defined by resource-bounded Turing machines.