Borges, Nerio and Bonet, Blai - Universal First-Order Logic is Superfluous for NL, P, NP and coNP

lmcs:1011 - Logical Methods in Computer Science, March 3, 2014, Volume 10, Issue 1
Universal First-Order Logic is Superfluous for NL, P, NP and coNP

Authors: Borges, Nerio and Bonet, Blai

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.

Source :
DOI : 10.2168/LMCS-10(1:15)2014
Volume: Volume 10, Issue 1
Published on: March 3, 2014
Submitted on: June 19, 2012
Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity


Consultation statistics

This page has been seen 80 times.
This article's PDF has been downloaded 58 times.