Publication:4237287
From MaRDI portal
zbMath0924.03049MaRDI QIDQ4237287
Publication date: 5 April 1999
complexity theory; finite model theory; descriptive complexity theory; reducibilities; Lindström quantifier; oracle Turing machines; relativized model of computation; oracle sets; capturing of relativized complexity classes
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
03D15: Complexity of computation (including implicit computational complexity)
03C13: Model theory of finite structures
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03D30: Other degrees and reducibilities in computability and recursion theory