二阶修正 KROM 逻辑的表达能力与复杂性
发布人：网站编辑
发布日期：2022-10-07
逻辑学研究 2022 年第 1 期，33–45 文章编号：1674-3202(2022)-01-0033-13
作者：冯世光 王克诩 赵希顺
摘 要：本文提出了二阶修正 KROM 逻辑，二阶扩展 KROM 逻辑（SO-EKROM）和二阶扩展修正 KROM 逻辑
，并对他们的表达能力和复杂性进行了研究。本文证明了在有序结构上，
与
等价，可以刻画 NL；而 SO-EKROM 与
等价，他们都可以刻画 co-NP。在所有结构上，
与
等价，他们也都可以刻画 co-NP。
关键词：计算复杂性；描述复杂性；KROM 逻辑；有穷模型论
中图分类号：B81
文献标识码：A