Relativization of Gurevich's Conjectures
share
Gurevich (1988) conjectured that there is no logic for P or for NP∩coNP. For the latter complexity class, he also showed that the existence of a logic would imply that NP∩coNP has a complete problem under polynomial time reductions. We show that there is an oracle with respect to which P does have a logic and P NP. We also show that a logic for NP∩coNP follows from the existence of a complete problem and a further assumption about canonical labelling. For intersection classes Σ^p_n ∩Π^p_n higher in the polynomial hierarchy, the existence of a logic is equivalent to the existence of complete problems.
READ FULL TEXT