Capturing the polynomial hierarchy by second-order revised Krom logic

DOI10.46298/LMCS-19(3:6)2023arXiv2207.09226MaRDI QIDQ6135775FDOQ6135775

Authors: Shiguang Feng, Xishun Zhao 

Publication date: 26 August 2023

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: 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 $Sigm{a}_1^1$-KROM${}^r$ equals $Sigm{a}_1^1$-KROM, and captures NL. On all finite structures, for $kgeq1$, we show that $Sigm{a}_k^1$ equals $Sigm{a}_{k+1}^1$-KROM${}^r$ if $k$ is even, and $P{i}_k^1$ equals $P{i}_{k+1}^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 $P{i}_2^1$-EKROM and equals $P{i}_1^1$. Both SO-EKROM and $P{i}_2^1$-EKROM capture co-NP on ordered finite structures.

Full work available at URL: https://arxiv.org/abs/2207.09226

zbMATH Keywords

polynomial hierarchydescriptive complexitysecond-order logicKrom logic

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Resolution for quantified Boolean formulas
• Title not available (Why is that?)
• The polynomial-time hierarchy
• Title not available (Why is that?)
• Languages that Capture Complexity Classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Capturing complexity classes by fragments of second-order logic
• Affine systems of equations and counting infinitary logic
• Relational queries computable in polynomial time
• Title not available (Why is that?)
• The expressive power of fixed-point logic with counting
• On the Descriptive Complexity of Linear Algebra
• Title not available (Why is that?)
• Approximations of isomorphism and logics with linear-algebraic operators
• Complexity and expressive power of second-order extended Horn logic

This page was built for publication: Capturing the polynomial hierarchy by second-order revised Krom logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6135775)