## More on Oracles and Quantifiers

```
Yachin Pnueli
Institut für Informatik
Freie Universität Berlin
email: pnueli@inf.fu-berlin.de
(joint work with Janos A. Makowski)
Report B 94-17
September 1994
```
```Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-94-17.ps.gz
```
More on Oracles and Quantifiers We continue the investigation of \cite{ar:MP94} into the relationship between classes of oracle using Turing machines and logics enhanced by Lindstr\"om quantifiers. Let \$\cL\$ be a logic (FOL or SOL) and let \$\cL[K]\$ be the enhancement of that logic with a Lindstr\"om quantifier for the set of structures \$K\$. We show that if for some sets of structures \$A,B,C\$ we have \$\cL[A,C] \subset \cL[B,C]\$ then also \$\cL[A] \subset \cL[B]\$. This has the complexity theoretic implication that, using the appropriate oracle computation model, finding an oracle \$K\$ such that \$\bL^K \subset \bP^K\$ constitutes a proof that \$\bL \subset \bP\$. Considering the case where \$\cL\$ is Second Order Logic or fragments of it we use the results of Meyer and Stockmeyer about the polynomial hierarchy to show that if \$\Sigma_i (\Pi_i)\$ is a fragment of \$SOL\$ capturing level \$\PS{i}\$ \$(\PP{i})\$ in the polynomial hierarchy, then the enhanced fragment \$\Sigma_i[K] (\Pi_i[K])\$ (for arbitrary \$K\$) captures \$\PSK{n}{K}\$ \$(({\Pi^p}_n)^K)\$ - that level relativized to an oracle for the set \$K\$. As a corollary the logic \$SOL[K]\$ captures the polynomial hierarchy relativized to oracle \$K\$ and has a prenex normal form where all second order quantifiers appear outer most.