Gurevich (1988) conjectured that there is no logic for $textsf{P}$ or for $textsf{NP}cap textsf{coNP}$. For the latter complexity class, he also showed that the existence of a logic would imply that $textsf{NP} cap textsf{coNP}$ has a complete problem under polynomial time reductions. We show that there is an oracle with respect to which $textsf P$ does have a logic and $textsf P etextsf{NP}$. We also show that a logic for $textsf{NP} cap textsf{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.
تحميل البحث