Logical reducibility and monadic NP

Abstract

It is shown that, by choosing appropriate encodings of instances as relational structures, several known polynomial-time many-one reductions can be described in first-order logic, and furthermore they are monadic. As a corollary, several known NP-complete problems in monadic NP are shown not to be in monadic co-NP. It is further shown that there is no monadic first-order reduction from connectivity to directed reachability, even in the presence of successor. Finally, some classes of syntactically restricted first-order reductions are shown to be incomparable.