论文标题
通过二阶修订的Krom逻辑捕获多项式层次结构
Capturing the polynomial hierarchy by second-order revised Krom logic
论文作者
论文摘要
我们研究二阶修订后的Krom Logic（So-Krom $^{r} $）的表达能力和复杂性。在有限的有限结构上，我们表明其存在片段$σ^1_1 $ -Krom $^r $等于$σ^1_1 $ -Krom，并捕获NL。在所有有限结构上，对于$ k \ geq 1 $，我们表明$σ^1_ {k} $等于$σ^1_ {k+1} $ - krom $ $^r $如果$ k $是偶数，而$π^1_ {k} $ equals $ qual $π^1_ {k+1} $ wif $ k $ k $结果提供了一种替代逻辑来捕获多项式层次结构。我们还引入了二阶Krom Logic（SO-EKROM）的扩展版。在有限的有限结构上，我们证明So-Ekrom倒入$π^{1} _ {2} $ - ekrom，并等于$π^1_1 $。 So-Ekrom和$π^{1} _ {2} $ - ekrom capture co-np capered有限结构。
We study the expressive power and complexity of second-order revised Krom logic (SO-KROM$^{r}$). On ordered finite structures, we show that its existential fragment $Σ^1_1$-KROM$^r$ equals $Σ^1_1$-KROM, and captures NL. On all finite structures, for $k\geq 1$, we show that $Σ^1_{k}$ equals $Σ^1_{k+1}$-KROM$^r$ if $k$ is even, and $Π^1_{k}$ equals $Π^1_{k+1}$-KROM$^r$ if $k$ is odd. The result gives an alternative logic to capture the polynomial hierarchy. We also introduce an extended version of second-order Krom logic (SO-EKROM). On ordered finite structures, we prove that SO-EKROM collapses to $Π^{1}_{2}$-EKROM and equals $Π^1_1$. Both SO-EKROM and $Π^{1}_{2}$-EKROM capture co-NP on ordered finite structures.
