论文标题
Gurevich猜想的相对化
Relativization of Gurevich's Conjectures
论文作者
论文摘要
Gurevich（1988）指出，$ \ textsf {p} $或$ \ textsf {np} \ cap \ textsf {conp} $没有逻辑。对于后一种复杂性类，他还表明逻辑的存在意味着$ \ textsf {np} \ cap \ textsf {conp} $在多项式时间缩短下存在一个完整的问题。我们表明，有一个甲骨文，$ \ textsf p $确实具有逻辑，$ \ textsf p \ ne \ textsf {np} $。我们还表明，$ \ textsf {np} \ cap \ textsf {conp} $的逻辑遵循了一个完整的问题的存在和关于规范标签的进一步假设。对于多项式层次结构中$capπ^p_n $ $σ^p_n \capπ^p_n $的相交类，逻辑的存在等效于存在完整问题。
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 \ne\textsf{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 $Σ^p_n \cap Π^p_n$ higher in the polynomial hierarchy, the existence of a logic is equivalent to the existence of complete problems.
