A syntactic tool for proving hardness in the Second Level of the Polynomial-Time Hierarchy

Edwin Pin, Nerio Borges

In the nineties Immerman and Medina initiated the search for syn- tactic tools to prove NP-completeness. In their work, amongst several results, they conjecture that the NP-complet…