The power of primitive positive definitions with polynomially many variables

DOI10.1093/logcom/exw005zbMath1387.08001OpenAlexW2324696293MaRDI QIDQ3133171

Magnus Wahlström, Victor Lagerkvist

Publication date: 13 February 2018

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

Full work available at URL: http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-139605

zbMATH Keywords

constraint satisfaction problemsco-clonepolynomially closed co-cloneprimitive positive definitionssuperpolynomially closed co-clone

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Operations and polynomials in algebraic structures, primal algebras (08A40)

Related Items (8)

Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem ⋮ The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems ⋮ Best-case and worst-case sparsifiability of Boolean CSPs ⋮ A Dichotomy Theorem for the Inverse Satisfiability Problem

This page was built for publication: The power of primitive positive definitions with polynomially many variables