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 i...

Full description

Saved in:
Bibliographic Details
Main Author: Cosmadakis, S.S.
Format: Conference Proceeding
Language:English
Subjects:
Encoding
Logic
NP-complete problem
Polynomials
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.< >
DOI:10.1109/SFCS.1993.366882