  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-completeness of a problem defined by the conjunction of
a sentence in Existential Second Order Logic with a First Order sentence,
necessarily imply the NP-completeness of the problem defined by the Existential
Second Order sentence alone. This is interesting because if true it would
justify the restriction heuristic pro- posed in Garey and Johnson in his
classical book on NP completeness, which roughly says that in some cases one
can prove NP- complete a problem A by proving NP-complete a problem B contained
in A. Borges and Bonet extend some results from Immerman and Medina and they
also prove for a host of complexity classes that the Immerman- Medina
conjecture is true when the First Order sentence in the conjunc- tion is
universal. Our work extends that result to the Second Level of the
Polynomial-Time Hierarchy.
