The power of primitive positive definitions with polynomially many variables

DOI10.1093/LOGCOM/EXW005MaRDI QIDQ3133171zbMATH OpenOpenAlexFDO

Authors Victor Lagerkvist, Magnus Wahlström

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

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

Recommendations

• Positive existential definability of multiplication from addition and the range of a polynomial
• Positive versions of polynomial time
• On the expression complexity of equivalence and isomorphism of primitive positive formulas
• Bounds and definability in polynomial rings
• On the strength of uniqueness quantification in primitive positive formulas
• On the number of sets definable by polynomials
• scientific article; zbMATH DE number 426121
• scientific article; zbMATH DE number 4148233
• scientific article; zbMATH DE number 3884129
• scientific article; zbMATH DE number 1428941

Cited in

(12)

• The number of clones determined by disjunctions of unary relations
• Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
• scientific article; zbMATH DE number 7536562 (Why is no real title available?)
• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• Sparsification lower bounds for list \(H\)-coloring
• A dichotomy theorem for the inverse satisfiability problem
• Positive primitive structures
• scientific article; zbMATH DE number 2162203 (Why is no real title available?)
• Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
• Best-case and worst-case sparsifiability of Boolean CSPs
• Finitely Many Primitive Positive Clones
• Best-case and worst-case sparsifiability of Boolean CSPs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3133171)