Monadic logical definability of NP-complete problems

DOI10.1007/BFB0022256MaRDI QIDQ4474839zbMATH OpenFDO

Authors Etienne Grandjean, Frédéric Olive

Publication date 21 July 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0022256

zbMATH Keywords

computational complexityfinite model theorylinear timemonadic second-order logicnondeterminismNP-complete problemrandom access machine

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• Monadic logical definability of nondeterministic linear time
• On monadic NP vs monadic co-NP
• STACS 2004
• MonadicNLIN and quantifier-free reductions
• Monotonicity and the Expressibility of NP Operators

Cited in

(11)

• Monadic logical definability of nondeterministic linear time
• A descriptive complexity approach to the linear hierarchy.
• Sorting, linear time and the satisfiability problem
• scientific article; zbMATH DE number 6387492 (Why is no real title available?)
• SAT in Monadic Gödel Logics: A Borderline between Decidability and Undecidability
• Logical Description of Monotone NP Problems
• Rudimentary Languages and Second‐Order Logic
• MonadicNLIN and quantifier-free reductions
• Monotone recursive definition of predicates and its realizability interpretation
• STACS 2004
• Complete problems for monotone NP

This page was built for publication: Monadic logical definability of NP-complete problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4474839)