Use this resource - and many more! - in your textbook!
AcademicPub holds over eight million pieces of educational content for you to mix-and-match your way.
Logical reducibility and monadic NP
By: Cosmadakis, S.S.;
1993 / IEEE / 0-8186-4370-6
This item was taken from the IEEE Periodical ' Logical reducibility and monadic NP ' It is shown that, by choosing appropriate encodings of instances as relational structures, several known polynomial-time many-one reductions can he 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.<
Syntactically Restricted First-order Reductions
Polynomial-time Many-one Reductions