Relativization of Gurevich's Conjectures

Abstract

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

accepted for publication in a volume of papers dedicated to Yuri Gurevich's 80th birthday