Capturing the polynomial hierarchy by second-order revised Krom logic

DOI10.46298/lmcs-19(3:6)2023arXiv2207.09226MaRDI QIDQ6135775

Zhao, Xishun, Unnamed Author, Shiguang Feng

Publication date: 26 August 2023

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

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

zbMATH Keywords

second-order logicpolynomial hierarchydescriptive complexityKrom logic

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Affine systems of equations and counting infinitary logic
• Capturing complexity classes by fragments of second-order logic
• The polynomial-time hierarchy
• Resolution for quantified Boolean formulas
• On the Descriptive Complexity of Linear Algebra
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• The expressive power of fixed-point logic with counting
• Complexity and expressive power of second‐order extended Horn logic