Constraint Satisfaction with Countable Homogeneous Templates

DOI10.1093/logcom/exi083zbMath1113.03026MaRDI QIDQ3430949

Jaroslav Nešetřil, Manuel Bodirsky

Publication date: 5 April 2007

Published in: Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/logcom/exi083

zbMATH Keywords

computational complexity; age; NP-complete; constraint satisfaction problem; \(\omega\)-categorical structure; clone of polymorphisms; countable homogeneous digraph; countable homogeneous relational structure; polymorphism preservation theorem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D15: Complexity of computation (including implicit computational complexity)

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

05C20: Directed graphs (digraphs), tournaments

03C05: Equational classes, universal algebra in model theory

03C52: Properties of classes of models

03C35: Categoricity and completeness of theories

Related Items

Introduction to the Maximum Solution Problem, \({\aleph_{0}}\)-categorical structures: endomorphisms and interpretations, More sublattices of the lattice of local clones, The complexity of equality constraint languages, Maximal infinite-valued constraint languages, Determining the consistency of partial tree descriptions, A survey of homogeneous structures