Logical characterization of bounded query classes. II: Polynomial-time oracle machines. (English) Zbl 0789.68059

Börger, Egon (ed.) et al., Computer science logic. 6th workshop, CSL ’92, San Miniato, Italy, September 28 - October 2, 1992. Selected papers. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 702, 410-424 (1993).
Summary: This paper is a companion to [I. A. Stewart, Lect. Notes Comput. Sci. 620, 470-479 (1992)] and continues the investigation of the logic \((\pm HP)^*[FO_ s]\), introduced in [I. A. Stewart, J. Comput. System Sci. 45, No. 1, 127-151 (1992; Zbl 0752.68041)], see also the author’s articles with the same title in [Ann. Soc. Math. Pol., Ser. IV, Fundam. Inf. 65-92, 93-105 (1993; Zbl 0782.68049, Zbl 0782.68050)]. In [I. A. Stewart, loc. cit.] the logics \(Bool[HP^ 1[FO_ s]]\), \((\pm HP)^ 1[FO_ s]\), and \((\pm DTC)^*[HP^*[FO_ s]]\) were studied with the latter two being shown to capture the complexity class \(L^{NP}\): the former was shown to capture the complexity class \(L^{NP}[O(1)]\), with the outcome being that it is extremely unlikely that \(Bool[HP^ 1[FO_ s]]\) is as expressible as either of the logics \((\pm HP)^ 1[FO_ s]\) or \((\pm DTC)^*[HP^*[FO_ s]]\) (\(Boll[HP^ 1[FO_ s]]\) is the Boolean closure of \(HP^ 1[FO_ s]\)).
We show that the logics \((\pm HP)^*[FO_ s]\) and \((\pm HP)^ 1[FO_ s]\) actually have the same expressibility: that is, all nested applications of the operator \(HP\) in a sentence of \((\pm HP)^*[FO_ s]\) can be replaced by a single application. Consequently, the hierarchy of logics \[ (NP=HP^ 1[FO_ s]\subseteq)(\pm HP)^ 1[FO_ s]\subseteq(\pm HP)^ 2[FO_ s]\subseteq\ldots\subseteq(\pm HP)^*[FO_ s] \] collapses to \((\pm HP)^ 1[FO_ s]\) ( a logic is equated with the class of problems described by the sentences of that logic). This result should be compared with the collapse of similar hierarchies of logics such as \[ (NL=)TC^ 1[FO_ s]=(\pm TC)^ 1[FO_ s]=(\pm TC)^ 2[FO_ s]=\ldots=(\pm TC)^*[FO_ s], \] as established in [N. Immerman, SIAM J. Comput. 16, 760-778 (1987; Zbl 0634.68034); ibid. 17, 935-938 (1988; Zbl 0668.68056)].
We achieve our results by providing logical characterizations of some bounded-query complexity classes contained within \(P^{NP}\) and by applying an existing result due to Buss and Hay. Bounded-query complexity classes are defined by restricting the access of an oracle Turing machine to its oracle by, for instance, limiting the number of oracle queries or the number of batches of parallel oracle queries made in any computation.
For the entire collection see [Zbl 0852.00039].


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)