Logical reducibility and monadic NP
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
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.Keywords
This publication has 22 references indexed in Scilit:
- On transitive closure logicPublished by Springer Nature ,2005
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- On Completeness for NP via projection translationsPublished by Springer Nature ,1992
- Finite-model theory—a personal perspectivePublished by Springer Nature ,1990
- Second-order and Inductive Definability on Finite StructuresMathematical Logic Quarterly, 1987
- Structure and complexity of relational queriesJournal of Computer and System Sciences, 1982
- The complexity of satisfiability problemsPublished by Association for Computing Machinery (ACM) ,1978
- The polynomial-time hierarchyTheoretical Computer Science, 1976
- Monadic generalized spectraMathematical Logic Quarterly, 1975
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971