Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfaction

DOI10.1093/logcom/exr011zbMath1283.68160arXiv1005.1141MaRDI QIDQ2893326

Manuel Bodirsky, Peter Jonsson, Timo von Oertzen

Publication date: 20 June 2012

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

Full work available at URL: https://arxiv.org/abs/1005.1141

zbMATH Keywords

linear programming; constraint satisfaction problems; complexity dichotomy; primitive positive definability; linear program feasibility

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C05: Linear programming

08A70: Applications of universal algebra in computer science

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)