On the Complexity of MMSNP

DOI10.1137/090778493zbMath1280.68106OpenAlexW2086423722MaRDI QIDQ2902910

Hubie Chen, Manuel Bodirsky, Tomás Feder

Publication date: 22 August 2012

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/090778493

zbMATH Keywords

computational complexityconstraint satisfaction problemscomplexity dichotomyexistential second-order logic

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)

Related Items (2)

Unnamed Item ⋮ Using model theory to find decidable and tractable description logics with concrete domains

This page was built for publication: On the Complexity of MMSNP