Universal First-Order Logic is Superfluous for NL, P, NP and coNP

Nerio Borges, Blai Bonet

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 dissertat…