二阶修正KROM逻辑的表达能力与复杂性

作者：冯世光^*; **诩; 赵希顺

来源：逻辑学研究, 2022, 15(01): 33-45.

• 计算复杂性
• 描述复杂性
• KROM逻辑
• 有穷模型论

本文提出了二阶修正KROM逻辑(SO-KROMr)，二阶扩展KROM逻辑(SO-EKROM)和二阶扩展修正KROM逻辑(SO-EKROMr)，并对他们的表达能力和复杂性进行了研究。本文证明了在有序结构上，Σ11-KROMr与Σ11-KROM等价，可以刻画NL；而SO-EKROM与П21-EKROM等价，他们都可以刻画co-NP。在所有结构上，П21-KROMr与П21-EKROMr等价，他们也都可以刻画co-NP。

• 单位
  中山大学; 南通大学