On Canonical Forms of Complete Problems via First-order Projections

Nerio Borges, Blai Bonet

The class of problems complete for NP via first-order reductions is known to be characterized by existential second-order sentences of a fixed form. All such sentences are built ar…