一句话：证明二阶修正 Krom 逻辑及其片段可逐层刻画多项式层级，并给出捕获 NL 与 co-NP 的新逻辑。
本文研究二阶修正 Krom 逻辑（SO-KROM^r）的表达力与复杂性，目标是寻找能刻画多项式层级（PH）的替代逻辑。作者在有序有限结构上证明存在片段 Σ^1_1-KROM^r 等价于 Σ^1_1-KROM 并捕获 NL；在所有有限结构上证明偶数 k 时 Σ^1_k = Σ^1_{k+1}-KROM^r，奇数 k 时 Π^1_k = Π^1_{k+1}-KROM^r，从而逐层捕获 PH。文章还引入扩展二阶 Krom 逻辑 SO-EKROM，在有序有限结构上证明其坍缩到 Π^1_2-EKROM 且等于 Π^1_1，且二者均捕获 co-NP。
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 $\Sigma^1_1$-KROM$^r$ equals $\Sigma^1_1$-KROM, and captures NL. On all finite structures, for $k\geq 1$, we show that $\Sigma^1_{k}$ equals $\Sigma^1_{k+1}$-KROM$^r$ if $k$ is even, and $\Pi^1_{k}$ equals $\Pi^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 $\Pi^{1}_{2}$-EKROM and equals $\Pi^1_1$. Both SO-EKROM and $\Pi^{1}_{2}$-EKROM capture co-NP on ordered finite structures.
@article{paperbot2204,
title = {Capturing the polynomial hierarchy by second-order revised Krom logic},
author = {Kexu Wang and Shiguang Feng and Xishun Zhao},
journal = {Logical Methods in Computer Science},
volume = {Volume 19, Issue 3},
year = {2023},
doi = {10.46298/lmcs-19(3:6)2023}
}