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

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

Manuel Bodirsky, Timo von Oertzen, Peter Jonsson

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 programmingconstraint satisfaction problemscomplexity dichotomyprimitive positive definabilitylinear program feasibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Applications of universal algebra in computer science (08A70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Constraint satisfaction and semilinear expansions of addition over the rationals and the reals ⋮ Unnamed Item ⋮ Tractability conditions for numeric CSPs ⋮ Minimal functions on the random graph ⋮ Schaefer's Theorem for Graphs

This page was built for publication: Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfaction