scientific article; zbMATH DE number 1272994
capturing of relativized complexity classescomplexity theorydescriptive complexity theoryfinite model theoryLindström quantifieroracle setsoracle Turing machinesreducibilitiesrelativized model of computation
Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Given some appropriate representation of finite models by binary strings, we say a logic \(\mathcal L\) captures a complexity class \(\mathcal C\) iff every language in \(\mathcal C\) corresponds to a class of finite models of a sentence over \(\mathcal L\) and, conversely, the set of representations of such a model class is always in \(\mathcal C\). (For background see the textbooks of \textit{H.-D. Ebbinghaus} and \textit{J. Flum} [Finite model theory (1995; Zbl 0841.03014)] and of \textit{N. Immerman} [Descriptive complexity (1999; Zbl 0918.68031)].) The thesis is about the capturing of relativized complexity classes, i.e., given a relativized model of computation one wants to specify for all oracle sets \(A\), a logic \({\mathcal L}^A\) which captures the class determined by the computation model and \(A\). Here it is required that the logic \({\mathcal L}^A\) depends on \(A\) only insofar as its formulas might contain a Lindström quantifier which is canonically derived from \(A\). After introducing some basic concepts from finite model theory and complexity theory, the author reviews several models of computations with oracles as introduced by \textit{T. Baker, J. Gill}, and \textit{R. Solovay} [SIAM J. Comput. 4, 431-442 (1975; Zbl 0323.68033)], \textit{R. E. Ladner} and \textit{N. A. Lynch} [Math. Syst. Theory 10, 19-32 (1976; Zbl 0341.68036)], \textit{J. Simon} [On some subrecursive reducibilities, Ph.D. dissertation, Stanford University (1977)], \textit{W. L. Ruzzo, J. Simon}, and \textit{M. Tompa} [J. Comput. Syst. Sci. 28, 216-230 (1984; Zbl 0573.68021)], \textit{C. B. Wilson} [Lect. Notes Comput. Sci. 223, 362-382 (1986; Zbl 0615.68039)], \textit{J. F. Buss} [J. Comput. Syst. Sci. 36, 351-378 (1988; Zbl 0657.68047)], \textit{J. A. Makowsky} and \textit{Y. B. Pnueli} [Lect. Notes Comput. Sci. 832, 189-222 (1994)], \textit{Frick} [Thesis, Univ. Freiburg (1996)], as well as previous work on capturing relativized complexity classes by \textit{E. Grädel} [Lect. Notes Comput. Sci. 440, 163-175 (1990)], \textit{I. A. Stewart} [Ann. Soc. Math. Pol., Ser. IV, Fundam. Inf. 18, 65-92 (1993; Zbl 0782.68049); Lect. Notes Comput. Sci. 832, 318-333 (1994)], \textit{H. Imhof} [J. Log. Comput. 7, 405-425 (1997; Zbl 0880.03012); Fixed point logics and generalized quantifiers in descriptive complexity, Thesis, Univ. Freiburg (1996; Zbl 0870.03015)], \textit{Y. B. Pnueli} [unpublished manuscript, 1994], and Frick (see above). The remaining parts of the thesis focus on the capturing of relativized classes which correspond to the various models of oracle Turing machines which run in alternating polynomial time, nondeterministic logarithmic space, or deterministic polynomial space.
- Program schemes, arrays, Lindström quantifiers and zero-one laws
- Capturing relativized complexity classes with Lindström quantifiers
- On Number of Lindenbaum's Oversystems of Propositional and Predicate Calculi
- scientific article; zbMATH DE number 4027448 (Why is no real title available?)
- Oracles and quantifiers
- A perspective on Lindström quantifiers and oracles
- Capturing complexity classes with Lindström quantifiers
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4237287)
