Subclasses of binary NP

DOI10.1093/LOGCOM/8.2.189MaRDI QIDQ4399718zbMATH OpenOpenAlexFDO

Authors Arnaud Durand, Clemens Lautemann, Thomas Schwentick

Publication date 28 July 1998

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/17a8dce0e5151714040b226381f4b0705998de09

zbMATH Keywords

descriptive complexityexistential second-order logic

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On bijections vs. unary functions
• The closure of monadic NP
• scientific article; zbMATH DE number 1775416
• On monadic NP vs monadic co-NP

Cited in

(12)

• Hybrid logic meets IF modal logic
• The closure of monadic NP
• Linear time and the power of one first-order universal quantifier
• Closure properties of locally finite \(\omega\)-languages
• Existential second-order logic and modal logic with quantified accessibility relations
• Semantic restrictions over second-order logic
• Comparing the Power of Games on Graphs
• On bijections vs. unary functions
• Expressiveness of logic programs under the general stable model semantics
• Turing-Complete Subclasses of CHR
• The logics for the complexity classes with limited non-determinism
• The flattening operator in team-based logics

This page was built for publication: Subclasses of binary NP

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