More on oracles and quantifiers
Y. B. Pnueli, Janos A. Makowski · Refubium (Universitätsbibliothek der Freien Universität Berlin) · 1994
We continue the investigation of MP94] into the relationship between classes of oracle using Turing machines and logics enhanced by Lindstr om quanti ers.Let L be a logic (FOL or SOL) and let LK] be the enhancement of that logic with a Lindstr om quanti er for the set of structures K. W e s h o w that if for some sets of structures A B C we h a ve LAC] L BC] t h e n a l s o LA] L B].This has the complexity theoretic implication that, using the appropriate oracle computation model, nding an oracle K such t h a t L K P K constitutes a proof that L P. Considering the case where L is Second Order Logic or fragments of it we use the results of Meyer and Stockmeyer about the polynomial hierarchy to show t h a t i f i(i) is a fragment of SOL capturing level P i ( P i ) in the polynomial hierarchy, then the enhanced fragment iK](iK]) (for arbitrary K) captures ( P n ) K (( p n) K ) -that level relativized to an oracle for the set K. As a corollary the logic SOLK] captures the polynomial hierarchy relativized to oracle K and has a prenex normal form where all second order quanti ers appear outer most.