Universal first-order logic is superfluous for NL, P, NP and CO NP

Abstract:

In this work we continue the syntactic study of completeness that began with the works of Immerman and Medina. In particular, we take a conjecture raised by Medina in his dissertation that says if a conjunction of a second-order and a first-order sentences defines an NP-complete problems via fops, then it must be the case that the second- order conjoint alone also defines a NP-complete problem. Although this claim looks very plausible and intuitive, currently we cannot provide a definite answer for it. However, we can solve in the affirmative a weaker claim that says that all "consistent" universal first-order sentences can be safely eliminated without the fear of losing completeness. Our methods are quite general and can be applied to complexity classes other than NP (in this paper: to NLSPACE, PTIME, and coNP), provided the class has a complete problem satisfying a certain combinatorial property. © N. Borges and B. Bonet.

Año de publicación:

2014

Keywords:

• First order projections
• Complexity classes
• NP completeness
• descriptive complexity
• Problems and reductions

Fuente:

scopus