Relativization of Gurevich's Conjectures

Gurevich (1988) conjectured that there is no logic for $\mathsf{\text{P}}$ or for $\mathsf{\text{NP}}\cap \mathsf{\text{coNP}}$. For the latter complexity class, he also showed that the existence of a logic would imply that $$\mathsf{\text{NP}}$ \cap $\mathsf{\text{coNP}}$$ has a complete problem under polynomial time reductions. We show that there is an oracle with respect to which $\mathsf{\text{P}}$ does have a logic and $\mathsf{\text{P}}\mathrm{\ne }\mathsf{\text{NP}}$. We also show that a logic for $$\mathsf{\text{NP}}$ \cap $\mathsf{\text{coNP}}$$ follows from the existence of a complete problem and a further assumption about canonical labelling. For intersection classes $\Sigma^p_n \cap \Pi^p_n$ higher in the polynomial hierarchy, the existence of a logic is equivalent to the existence of complete problems.