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

Abstract:

In this paper we prove that ∀FO, the universal fragment of first-order logic, is superfluous in Σ2p and Π2p. As an example, we show that this yields a syntactic proof of the Σ2p-completeness of value-cost satisfiability. The superfluity method is interesting since it gives a way to prove completeness of problems involving numerical data such as lengths, weights and costs and it also adds to the programme started by Immerman and Medina about the syntactic approach in the study of completeness.

Año de publicación:

2019

Keywords:

• Computational complexity
• descriptive complexity
• Graph Theory
• MATHEMATICAL LOGIC

Fuente:

scopus