Loading [MathJax]/jax/output/HTML-CSS/jax.js

Kexu Wang ; Shiguang Feng ; Xishun Zhao - Capturing the polynomial hierarchy by second-order revised Krom logic

lmcs:9812 - Logical Methods in Computer Science, July 14, 2023, Volume 19, Issue 3 - https://doi.org/10.46298/lmcs-19(3:6)2023
Capturing the polynomial hierarchy by second-order revised Krom logicArticle

Authors: Shiguang Feng ; Kexu Wang ORCID; Xishun Zhao ; Yuping Shen

    We study the expressive power and complexity of second-order revised Krom logic (SO-KROMr). On ordered finite structures, we show that its existential fragment Σ11-KROMr equals Σ11-KROM, and captures NL. On all finite structures, for k1, we show that Σ1k equals Σ1k+1-KROMr if k is even, and Π1k equals Π1k+1-KROMr 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 Π12-EKROM and equals Π11. Both SO-EKROM and Π12-EKROM capture co-NP on ordered finite structures.


    Volume: Volume 19, Issue 3
    Published on: July 14, 2023
    Accepted on: May 30, 2023
    Submitted on: July 20, 2022
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity

    Classifications

    Mathematics Subject Classification 20201

    Consultation statistics

    This page has been seen 2131 times.
    This article's PDF has been downloaded 471 times.