Universal first-order logic is superfluous in the second level of the polynomial-time hierarchy

DOI10.1093/jigpal/jzz009zbMath1492.68058MaRDI QIDQ5865564

Nerio Borges, Edwin Pin

Publication date: 9 June 2022

Published in: Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/jigpal/jzz009

zbMATH Keywords

computational complexity; graph theory; mathematical logic; descriptive complexity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

03B70: Logic in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

68Q19: Descriptive complexity and finite models